2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How did you manage to compile expressions like source + offset * size? AFAIK a compiler needs to know the size of the objects pointed to, so it can scale the addend properly, and the size of data pointed by void* source is undefined. \$\endgroup\$ – CiaPan Jun 8 '16 at 8:45
  • 1
    \$\begingroup\$ @CiaPan source is a void*, so that source + offset * size means that "move offset * size bytes forward from source. Also, working with void* is the only way to simulate generic programming in C. \$\endgroup\$ – coderodde Jun 8 '16 at 8:47
  • 1
    \$\begingroup\$ in mergesort_impl() what is tmp? You never actually use it or assign a value to it. \$\endgroup\$ – pacmaninbw Jun 11 '16 at 15:38
  • \$\begingroup\$ @pacmaninbw Good point. It's just junk I forgot to remove from the code. \$\endgroup\$ – coderodde Jun 11 '16 at 15:40
  • 1
    \$\begingroup\$ Ah! I see now, the register keyword.. \$\endgroup\$ – coderodde Jun 11 '16 at 16:58
1
\$\begingroup\$

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...?
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ I am not quite positive, but it appears that I did exactly just that. In a trivial implementation, in each invocation of the main sort routine, people create two arrays, (left + right) copy the data to them, and merge from the left + right to the actual input array. I don't do this: I just merge from the source array to the target array, without allocating auxiliary memory, and at the next recursion level I change the roles of the source + target array. In the main function, I allocate (and copy) once the memory and call the implementation routine such that the stuff ends up in the input array \$\endgroup\$ – coderodde Jun 8 '16 at 9:21
  • \$\begingroup\$ Write down the contract for sort_helper(). Does it or doesn't it move the data from src to dst? \$\endgroup\$ – Deduplicator May 23 '17 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.