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