Mergesort Criticism in C

Question

I have written a merge sort in C and would like any advice on how to improve it. Any advice helps to make the code better!

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

static void mergesort_helper(void *array, uint32_t index, uint32_t length, size_t size_element, int32_t compare(void *, void *), void *storage)
{
   uint32_t i, j, k;
   if(length == 1)
   {
      /*printf("\n%d, %d\n", index, length);*/
      return;
   }

   mergesort_helper(array, index, length / 2, size_element, compare, storage);

   if(length % 2 == 0)
      mergesort_helper(array, (index + (index + length)) / 2, length / 2, size_element, compare, storage);
   else
      mergesort_helper(array, (index + (index + length)) / 2, length / 2 + 1, size_element, compare, storage);

   /*sorting part*/
   i = index;
   j = (index + (index + length)) / 2;
   k = 0;
   while(i < (index + (index + length)) / 2 || j < (index + length))
   {
      if(i < (index + (index + length)) / 2 && (compare(array + i * size_element, array + j * size_element) <= 0 || j >= (index + length)))
      {
          memcpy(storage + k * size_element, array + i * size_element, size_element);
          i++;
      }
      else if(j < (index + length) && (compare(array + i * size_element, array + j * size_element) > 0) || i >= (index + (index + length)) / 2)
      {
          memcpy(storage + k * size_element, array + j * size_element, size_element);
          j++;
      }
      k++;
   }
   memcpy(array + index * size_element, storage, length * size_element);
}

/*
   array -  to be sorted
   length - exclusive
   size_element - how big is one element
*/
void mergesort(void *array, uint32_t length, size_t size_element, int32_t compare(void *, void *))
{
   void *storage;
   if(length == 0)
      return;

   storage = malloc(size_element * length);
   mergesort_helper(array, 0, length, size_element, compare, storage);
   free(storage);
}


/*user code*/
int32_t compare(void *ptr1, void *ptr2)
{
   int32_t *temp_ptr1, *temp_ptr2;
   temp_ptr1 = (int32_t *)ptr1;
   temp_ptr2 = (int32_t *)ptr2;

   if(*temp_ptr1 < *temp_ptr2)
      return -1;
   else if(*temp_ptr1 > *temp_ptr2)
      return 1;

   return 0;
}

int main(void)
{
   uint32_t i;
   int32_t array[] = {6, 4, 3, 2, 7, -100, 1, 0, 5, 8, -100, 8};

   for(i = 0; i < sizeof(array) / sizeof(array[0]); i++)
   {
      printf("%d ", array[i]);
   }
   printf("\n");

   mergesort(array, sizeof(array) / sizeof(array[0]), sizeof(array[0]), &compare);

   for(i = 0; i < sizeof(array) / sizeof(array[0]); i++)
   {
      printf("%d ", array[i]);
   }
   printf("\n");
   return 0;
}

Answer 1

Avoid code duplication

Your code is more verbose than necessary, because you are repeating a lot of things unnecessarily, or write things in a more complex way than necessary. For example:

(index + (index + length)) / 2

This looks really weird, and is actually equivalent to:

index + length / 2

Which makes much more sense. Even with that change, that expression is used a lot in the code, so it's best to give it a name:

uint32_t middle = index + length / 2;

You also duplicated a call to mergesort_helper() in order to handle odd and even cases of length. However, you don't have to if you write it like so:

uint32_t middle = index + length / 2;
uint32_t end = index + length;

mergesort_helper(array, index, middle - index, size_element, compare, storage);
mergesort_helper(array, middle, end - middle, size_element, compare, storage);

You might also want to consider renaming index to start.

Use const for pointer arguments in compare()

Since the function compare() should not modify the elements it is comparing, the arguments should be pointers to const:

int32_t compare(const void *ptr1, const void *ptr2) {
   const int32_t *temp_ptr1 = ptr1;
   const int32_t *temp_ptr2 = ptr2;
   ...
}

Optimizing the while-loop

There are a few minor changes that can be made to speed up the while-loop a little bit. First, calling compare() is probably going to be the most expensive operation, so you would want to avoid calling it if possible. Rearrange the order in which you check things to make use of short-circuiting:

if(i < middle && (j >= end || compare(...)))

In the above, compare() will only be called if i < middle is true and j >= end is false.

Another possible optimization is realizing that if i >= middle || j >= end, you know you only need to copy the remainder of one side of the midpoint. Instead of doing that element by element, you could do that in one large memcpy(). It also simplifies the if-statements in the while-loop, like so:

while (i < middle && j < end) {
    if (compare(array + i * size_element, array + j * size_element) <= 0) {
        memcpy(storage + k * size_element, array + i * size_element, size_element);
        i++;
    } else {
        memcpy(storage + k * size_element, array + j * size_element, size_element);
        j++;
    }

    k++;
}

/* Copy the remainder */
if (i < middle) {
    memcpy(storage + k * size_element, array + i * size_element, size_element * (middle - i));
} else {
    memcpy(storage + k * size_element, array + j * size_element, size_element * (end - j));
}

The above has also the advantage that compare() is only called once every iteration, whereas in your original code it could have been called twice.

Avoid void pointer arithmetic

Lau G mentioned void pointers, and indeed doing arithmetic on void pointers is illegal. The simple workaround is to cast it to a char * first:

static void mergesort_helper(void *array_ptr, ...)
{
    char *array = array_ptr;
    ...

To catch these sort of issues, enable strict compiler warnings. For GCC and Clang, use -Wall -pedantic. Fix all the warnings the compiler produces.

Answer 2

Interface

A more appropriate type for length would be size_t. And I'd expect the compare argument to be a function returning plain int, and accepting pointers to const void.

Test program

The test program could be improved with the addition of a is_sorted() function to confirm the result and return the appropriate success/failure value. I would recommend saving the repeated calculation of array length into a variable:

const size_t length = sizeof array / sizeof array[0];

I suggest reducing the scope of i to just the loops:

for (size_t i = 0;  i < length;  ++i)

Comparator

We don't need to declare and assign separately, and we don't need to write a cast to convert from void*:

   int32_t *temp_ptr1, *temp_ptr2;
   temp_ptr1 = (int32_t *)ptr1;
   temp_ptr2 = (int32_t *)ptr2;

I would write that as:

   int32_t const *a = ptr1;
   int32_t const *b = ptr2;

I took the liberty to use shorter and more distinct names, which are easier to tell apart where they are used.

There's a well-known trick for returning -1, 0 or +1 from comparisons, relying on the fact that boolean values are 0 and 1:

   return (*a > *b) - (*a < *b);

Helper function

Again, reduce the scope of variables, and declare them where they are assigned, to reduce chance of using uninitialised values.

We have a repeated calculation of (index + (index + length)) / 2. Not only could this be given a name, but we can remove the error caused when the sum is large enough to overflow:

const size_t mid_index = index + length / 2;

We have a lot of invalid pointer arithmetic such as array + i * size_element. Because array is pointer to void, addition is not defined - we probably want to change the argument's type to char*. Similarly, storage should also be char*.

Sort function

We allocate memory, but blindly continue when malloc() returns a null pointer, leading to Undefined Behaviour. Don't do that!

Answer 3

I'm not too confident with my knowledge on (void) pointers so I will avoid giving feedback on the pointer related stuff.

Unnecessary if...else statement.

if(length % 2 == 0)
    mergesort_helper(array, (index + (index + length)) / 2, length / 2, size_element, compare, storage);
else
    mergesort_helper(array, (index + (index + length)) / 2, length / 2 + 1, size_element, compare, storage);

Can be turned into:

mergesort_helper(array, (index + (index + length)) / 2, length / 2 + (length % 2), size_element, compare, storage);

Minor improvement to the length check in mergesort.

When the array is of length 1 it is possible to return early as well, because an array of length 1 is already sorted.

void mergesort(void *array, const uint32_t length, const size_t size_element, int32_t compare(void *, void *))
{
    ...
    if (length <= 1) { return; }
    ...
}

Use const

length and size_element don't change in the mergesort and mergesort_helper functions. This is also the case for index in the mergesort_helper function. It would be best to use the const keyword to indicate this, this can also be helpful to the compiler.

void mergesort(void *array, const uint32_t length, const size_t size_element, int32_t compare(int32_t *, int32_t *))
static void mergesort_helper(void *array, const uint32_t index, const uint32_t length, const size_t size_element, int32_t compare(int32_t *, int32_t *), void *storage)

Styling & Readability

Some of these are opinionated so you can use what you see fit.

• Use an indentation of 4 spaces instead of 3.
• Use a space between if/while/for and (
• Use brackets on if...else statements even if they are one line. There's a chance more lines will be added to the if...else statement later on. Forgetting to add brackets when this happens can lead to bugs that could have been avoided if brackets where added from the start.
• Merge sort consists of two words so merge_sort would be more appropriate.
• (index + (index + length)) / 2 represents the middle index it would make the code easier to read if it was assigned to a const variable.

static void mergesort_helper(void *array, const uint32_t index, const uint32_t length, const size_t size_element, int32_t compare(void *, void *), void *storage)
{
    uint32_t i, j, k;
    if (length == 1)
    {
        /*printf("\n%d, %d\n", index, length);*/
        return;
    }

    const uint32_t m_index = (index + (index + length)) / 2;

    mergesort_helper(array, index, length / 2, size_element, compare, storage);

    mergesort_helper(array, m_index, length / 2 + length % 2, size_element, compare, storage);

    /*sorting part*/
    i = index;
    j = m_index;
    k = 0;

    while (i < m_index || j < (index + length))
    {
        if (i < m_index && (compare(array + i * size_element, array + j * size_element) <= 0 || j >= (index + length)))
        {
            memcpy(storage + k * size_element, array + i * size_element, size_element);
            i++;
        }
        else if (j < (index + length) && (compare(array + i * size_element, array + j * size_element)> 0 || i >= m_index))
        {
            memcpy(storage + k * size_element, array + j * size_element, size_element);
            j++;
        }

        k++;
    }

    memcpy(array + index * size_element, storage, length * size_element);
}

Maybe it is possible to make the if..else statement in the while loop of mergesort_helper more clean. If it is 100% certain either the if or if else is true, it would be possible to just make the if else statement an else statement.

Answer 4

1. Keep your includes ordered for maintainability and shorter diffs.
   The separate sorted groups should be in order: This files header (first to ensure it remains self-contained), external libraries (standard and additional), this project's headers.

   #include <assert.h>
   #include <stdio.h>
   #include <stdlib.h>
   #include <string.h>
   

2. There are many ways to represent an array-slice, but fundamentally you only need a pointer to the first element, and the count. The first element of the underlying array, if you even know it, is of no interest at all.

3. If the only way to get to some memory is by a function-argument, marking that restrict allows better optimization and is good documentation.

4. Instead of special-casing remainder / no remainder when determining half the count, just subtract the range handled from the whole. It's less error-prone.

5. Your code for merging is over-complicated because you don't handle all the rest at once when one of the sorted sequences runs empty. That's also inefficient.

6. You only need half the scratch-space if you move the left sequence out before merging to the destination, instead of merging in the scratch-space and copying the result back.

7. There is a type in C dedicated for object-size and thus also array-indices: size_t.
   Use it where appropriate.

8. void*-arithmetic (assuming sizeof(void) == 1) is a gcc extension. There is no reason to use it as you could just use a char* instead and be strictly conformant.

9. Comparison-functions in C traditionally return int, the significance being smaller, equal, or bigger to zero. So, why would you ever consider anything else?

10. If a function should not modify arguments passed by pointer, let the type reflect it. Const-correctness allows the compiler to help catch errors.

11. Consider adding a typedef to avoid repeating the comparator's type.

12. Even though zero is an invalid input for mergesort_helper(), I personally think reasoning is easier if the guard-clause reads < 2 than == 1.

13. Avoid overly long lines. Horizontal scrolling kills readability and thus maintainability.

14. While mixing declarations and statements is strictly speaking not allowed before C99, everybody already implemented it already because it is so useful.

    Defer declaring a variable until you have the proper value to initialize it to. Don't initialize it to some arbitrary value, and don't leave it uninitialized if you can help it. That avoids errors and makes eases understanding.

typedef int (*comparator)(const void*, const void*);

static void mergesort_helper(
    char* restrict p,
    size_t n,
    size_t s,
    comparator f,
    char* restrict scratch
) {
    if (n < 2) return;
    const size_t mid = n / 2;
    mergesort_helper(p, mid, s, f, scratch);
    mergesort_helper(p + mid * s, n - mid, s, f, scratch);
    memcpy(scratch, p, mid * s);
    char *aa = scratch, *ab = scratch + mid * s, *ba = p + mid * s, *bb = p + n * s;
    while (aa != ab && ba != bb) {
        char** x = f(aa, ba) <= 0 ? &aa : &ba;
        memcpy(p, *x, s);
        p += s;
        *x += s;
    }
    memcpy(p, aa, ab - aa);
}

15. While immediately returning if no elements should be sorted is enough to preserve the invariants of your code, I would also do so for a single element. That is, if I optimized for the trivial case at all, which is a pessimization of the far more important common case. Thanks to changing the guard-clause in mergesort_helper() and thus its invariants, doing so is no longer needed.

16. You really should handle insufficient memory, if only by calling abort().

17. As mergesort() is the entry-point, I would set a few assert()s for sanity-testing during development.

/*
    p   - array to be sorted
    n   - number of elements
    s   - size of each element
    f   - comparator
*/
void mergesort(void * restrict p, size_t n, size_t s, comparator f) {
    assert(s && n <= (size_t)-1 / s && (!n || (f && p)));
    void* scratch = malloc(n / 2 * s);
    if (!scratch && n / 2) {
        fprintf(stderr, "malloc() failed for mergesort().\n");
        abort();
    }
    mergesort_helper(p, n, s, f, scratch);
    free(scratch);
}

18. There is a simpler idiomatic way to define three-way-comparison even if simply subtracting doesn't fit.

19. Do not cast from or to void*. Implicit conversions work and are less error-prone.

static int compare(const void* pa, const void* pb) {
    const int32_t *a = pa, *b = pb;
    return (*a > *b) - (*a < *b);
}

20. You have exactly one test-case, and that for the typical case. Automate it (by adding a corresponding is_sorted() tester), and try with one and zero elements to at least test the obvious corner cases.

21. Using the wrong format-specifier for printf is a bug.

22. return 0; is implicit for main() since C99.

23. Return an error if your program ends with a detected failure.

int is_sorted(const void * restrict p, size_t n, size_t s, comparator f) {
    assert(s && n <= (size_t)-1 / s && (!n || (f && p)));
    if (n--)
        for (const char* q = p; n--; q += s)
            if (f(q, q + s) > 0)
                return 0;
    return 1;
}

static int test(int32_t array[], size_t n) {
    printf("%zu: ", n);
    for (size_t i = 0; i < n; ++i)
        printf("%" PRId32 " ", array[i]);
    printf("\n");

    mergesort(array, n, sizeof *array, &compare);

    int res = is_sorted(array, n, sizeof *array, &compare);

    printf(res ? "OK: " : "FAIL: ");
    for (size_t i = 0; i < n; ++i)
        printf("%" PRId32 " ", array[i]);
    printf("\n");

    return res;
}

int main() {
    int32_t array[] = {6, 4, 3, 2, 7, -100, 1, 0, 5, 8, -100, 8};

    return !test(array, sizeof array / sizeof *array)
        || !test(array, 1)
        || !test(array, 0)
        || !test(0, 0);
}

See it all coming together live on coliru.

Answer 5

TLDR: in order to improve performance while keeping it simple, switch to insertion sort for small arrays.

Congratulations on choosing mergesort! This is a great choice. It is very elegant, stable and can achieve great performance without the code turning in an horrible mess as is typically the case with quicksort.

There are many answers already so I will chose a different angle.

I do not know what kind of improvement you are looking for, but if performance is a concern, the cost of recursion is going to be prohibitive for small (sub-)arrays.

One good way to fix this is to test for the size of the array and use insertion sort instead if the number of entries is below a limit. Start with a limit of 8 and then try other values later if you are into performance tuning.

You could alternatively write a non-recursive version of mergesort. All you would achieve is that the code would be less readable, though. Don't do it! And insertion sorts makes fewer comparisons than merge sort on smalls arrays anyway.

Another more complex way would be to investigate timsort. Timsort is the state of the art of adaptative merge algorithms nowadays. Many language runtimes implement the standard sorting algorithm as timsort. The complexity of the code increase greatly, though.

Finally, if you enjoy experimentation, here is a last idea. You could figure out that internal sorts only exist nowadays in the special case where the array is small enough to fit in the CPU's level 1 cache. In all other cases, what you are doing is actually an external sort. And guess which algorithm shines particularly for this purpose? Yes, right, it is indeed mergesort! Thus you could try to implement a cache-aware k-way mergesort or a cache-aware timsort. This would some extra layers of complexity as you would need to write some architecture-dependent code. But who knows what results such an experiment would yield?

Another way to improve performance for large item sizes could be to check for the size of elements and apply mergesort to an array of pointers to the elements instead of the array of elements itself. As I recall, the implementation of qsort() in glibc does this.

Anyway, these are only a few ideas from the top of my head. Do what suits you best and have fun!

Answer 6

Create simple code for simple tasks don't overcomplicate it, and better name your functions

#include <stdio.h>
#include <stdlib.h>
 
void merge (int *a, int n, int m) {
    int i, j, k;
    int *x = malloc(n * sizeof (int));
    for (i = 0, j = m, k = 0; k < n; k++) {
        x[k] = j == n      ? a[i++]
             : i == m      ? a[j++]
             : a[j] < a[i] ? a[j++]
             :               a[i++];
    }
    for (i = 0; i < n; i++) {
        a[i] = x[i];
    }
    free(x);
}
 
void merge_sort (int *a, int n) {
    if (n < 2)
        return;
    int m = n / 2;
    merge_sort(a, m);
    merge_sort(a + m, n - m);
    merge(a, n, m);
}

Reference code http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#C