Mergesort algorithm in C

Question

I have this mergesort implementation that has exactly the same API as qsort:

mergesort.h:

#ifndef MERGESORT_H
#define MERGESORT_H

#include <stdlib.h>

#ifdef  __cplusplus
extern "C" {
#endif

    void my_mergesort(void* base, 
                      size_t num, 
                      size_t size, 
                      int (*compar)(const void*, const void*));

#ifdef  __cplusplus
}
#endif

#endif  /* MERGESORT_H */

mergesort.c:

#include "mergesort.h"
#include <stdlib.h>
#include <string.h>

static void mergesort_impl(void* source,
                           void* target,
                           void* tmp,
                           size_t size,
                           size_t offset,
                           size_t range_length,
                           int (*compar)(const void*, const void*)) 
{
    if (range_length < 2) 
    {
        return;
    }

    size_t half_range_length = range_length >> 1;

    mergesort_impl(target, 
                   source, 
                   tmp,
                   size, 
                   offset, 
                   half_range_length,
                   compar);

    mergesort_impl(target, 
                   source, 
                   tmp,
                   size, 
                   offset + half_range_length, 
                   range_length - half_range_length,
                   compar);

    void* left_subarray_pointer = source + offset * size;
    void* left_subarray_pointer_bound = left_subarray_pointer +
                                        half_range_length * size;

    void* right_subarray_pointer = left_subarray_pointer_bound;
    void* right_subarray_pointer_bound = source + (offset + range_length) 
                                                * size;

    void* target_array_pointer = target + offset * size;

    while (left_subarray_pointer < left_subarray_pointer_bound
            && right_subarray_pointer < right_subarray_pointer_bound) 
    {
        if (compar(right_subarray_pointer, left_subarray_pointer) < 0)
        {
            memcpy(target_array_pointer, right_subarray_pointer, size);
            target_array_pointer   += size;
            right_subarray_pointer += size;
        }
        else 
        {
            memcpy(target_array_pointer, left_subarray_pointer, size);
            target_array_pointer  += size;
            left_subarray_pointer += size;
        }
    }

    memcpy(target_array_pointer, 
           left_subarray_pointer, 
           left_subarray_pointer_bound - left_subarray_pointer);

    memcpy(target_array_pointer, 
           right_subarray_pointer, 
           right_subarray_pointer_bound - right_subarray_pointer);
}


void my_mergesort(void* base, 
                  size_t num, 
                  size_t size, 
                  int (*compar)(const void*, const void*))
{
    void* tmp = malloc(size);
    void* aux = malloc(num * size);
    memcpy(aux, base, num * size);
    mergesort_impl(aux, base, tmp, size, 0, num, compar);
    free(tmp);
    free(aux);
}

main.c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/time.h>
#include "mergesort.h"

static int compar(const void* a, const void* b) 
{
    return (*(int*) a) - (*(int*) b);
}

static int* create_random_int_array(size_t length)
{
    int* array = malloc(length * sizeof(int));

    srand(time(NULL));

    for (size_t i = 0; i < length; ++i) 
    {
        array[i] = rand() % (1000 * 1000);
    }

    return array;
}

static long get_milliseconds() 
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec * 1000 + tv.tv_usec / 1000;
}

int arrays_are_same(int* arr1, int* arr2, size_t length) 
{
    for (size_t i = 0; i < length; ++i) 
    {
        if (arr1[i] != arr2[i]) 
        {
            return 0;
        }
    }

    return 1;
}

static const size_t ARRAY_SIZE = 10 * 1000 * 1000;

int main() {
    int* arr1 = create_random_int_array(ARRAY_SIZE);
    int* arr2 = malloc(sizeof(int) * ARRAY_SIZE);
    memcpy(arr2, arr1, sizeof(int) * ARRAY_SIZE);

    long start_time = get_milliseconds();
    my_mergesort(arr1, ARRAY_SIZE, sizeof(int), compar);
    long end_time = get_milliseconds();

    printf("my_mergesort took %ld milliseconds.\n", end_time - start_time);

    start_time = get_milliseconds();
    qsort(arr2, ARRAY_SIZE, sizeof(int), compar);
    end_time = get_milliseconds();

    printf("qsort took %ld milliseconds.\n", end_time - start_time);

    printf("Arrays are identical: %d\n", arrays_are_same(arr1, 
                                                         arr2,
                                                         ARRAY_SIZE));

    free(arr1);
    free(arr2);
}

Any critique is much appreciated. I am especially interested to hear how can I improve the performance of my merge sort, as it runs around 3 times slower than qsort.

Answer 1

The most important improvement IMHO would be avoiding copying data back and forth.

You can allocate just one additional block of memory and copy all your input to it just once. That will be the source for the final merge. And the input array will be a source for one-but-last merge...

Here is an outline:

merge(char *dest, char *src1, int num1, char *src2, int num2, size, cmpfun)
{
    // quite obvious, isn't it...?
}

sort_helper(char *dst, char *src, num, size, cmpfun)
{
    if(num > 1)
    {
        half = num / 2;
        sort_helper(src,             dst,             half,       size, cmpfun);
        sort_helper(src + half*size, dst + half*size, num - half, size, cmpfun);

        merge(dst, src, half,  src + half*size, num - half, size, cmpfun);
    }
}

sort(void *arr, int num, int size, cmpfun)
{
    if(num > 1)
    {
        char *tmp = malloc(num * size);     // the only malloc()
        if(tmp != NULL)
        {
            memcpy(tmp, arr, num * size);   // the only memcpy()

            sort_helper((char* )arr, tmp, num, size, cmpfun);

            free(tmp);
        }
        else
        {
            // some error handling for malloc() failure...?
        }
    }
}