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; }