Mergesort in C

Mergesort was invented by John Von Neumann in 1945, and is the archetypal divide-and-conquer algorithm. This is an implementation in C, with the same interface as the standard qsort function.

void *memdup(const void *mem, size_t size)
{
void *buf = malloc(size);
if (buf) {
memcpy(buf, mem, size);
}
return buf;
}

void merge(void *arr, unsigned int left, unsigned int middle, unsigned int right,
size_t element_size, int (*compare)(const void *, const void *))
{
unsigned int i, j, k;
unsigned int nl = middle - left + 1;
unsigned int nr = right - middle;

void *larr = memdup(arr + left * element_size, nl * element_size);
void *rarr = memdup(arr + (middle + 1) * element_size, nr * element_size);

for (i = 0, j = 0, k = left; i < nl && j < nr; k++) {
if (compare(larr + i * element_size, rarr + j * element_size) <= 0) {
memcpy(arr + k * element_size, larr + i * element_size, element_size);
i++;
}
else {
memcpy(arr + k * element_size, rarr + j * element_size, element_size);
j++;
}
}

memcpy(arr + k * element_size, larr + i * element_size, (nl - i) * element_size);
k += nl - i;
memcpy(arr + k * element_size, rarr + j * element_size, (nr - j) * element_size);

free(larr);
free(rarr);
}

void mergesort_recursive(void *arr, unsigned int left, unsigned int right, size_t element_size,
int (*compare)(const void *, const void *))
{
if (left < right) {
unsigned int middle = (left + right) / 2;

mergesort_recursive(arr, left, middle, element_size, compare);
mergesort_recursive(arr, middle + 1, right, element_size, compare);

merge(arr, left, middle, right, element_size, compare);
}
}

void mergesort(void *arr, size_t len, size_t element_size,
int (*compare)(const void *, const void *))
{
mergesort_recursive(arr, 0, len - 1, element_size, compare);
}


An example program:

static int compare_chars(const void *v1, const void *v2)
{
const char *p1 = v1;
const char *p2 = v2;
if (*p1 < *p2) {
return - 1;
}
if (*p1 > *p2) {
return 1;
}
return 0;
}

int main(void)
{
char str1[] = "QWERTYUIOP";
const size_t len = strlen(str1);
char *str2 = malloc(len + 1);
strcpy(str2, str1);
mergesort(str2, len, 1, compare_chars);
printf("%s\n", str2);
free(str2);
return 0;
}