Mergesort in C

Introduction

Quicksort is most people’s go to sort function and that’s not a bad thing because it’s a really good general purpose sorting algorithm. A good implementation is really fast and, being an in place algorithm, it uses very little memory.

The big drawback of Quicksort is that it’s non-stable. This means there are some situations where using Quicksort a deal breaker and can’t be used. Enter Mergesort which is stable.

That said, don’t think you should always use Mergesort instead of Quicksort. Mergesort is slower and uses more memory. A general rule of thumb is to use Quicksort unless you need a stable sort, then use Mergesort.

Big-O complexity:

The Algorithm Explained

This is a stable, not in place algorithm.

Mergesort splits the array into a series of 1 element arrays. This sounds really weird but bear with me. Then compare each subarray with its adjacent subarray and combine them. The 1 element arrays will be combined into a set of 2 element arrays which will be combined into 4 element arrays and so forth. Each combined subarry will be compared to the other adjacent subarrays.

If there is an odd number of elements the last 3, 1 element arrays will be combined into 2 and 1 element arrays, then combined into a 3 element array. From there the last array will always have an odd number of elements.

Example to illustrate the process.

array:  [1 9 3 5 8 2 4]
arrays: [1 9 3 5] [8 2 4]
arrays: [1 9] [3 5] [8 2] [4]
arrays: [1] [9] [3] [5] [8] [2] [4]
arrays: [1 9] [3 5] [8 2] [4]
arrays: [1 3 5 9] [2 4 8]
arrays: [1 2 3 4 5 8 9]
array:  [1 2 3 4 5 8 9]

The algorithm:

void merge_sort(void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *))
{
    char   *left;
    char   *right;
    size_t  ls;
    size_t  rs;
    size_t  mid;
    size_t  i;
    size_t  j;
    size_t  k;

    if (base == NULL || nel < 2 || width == 0 || cmp == NULL)
        return;

    /* Find the mid and deal with an odd number of elements. */
    mid = nel/2;
    ls  = mid;
    rs  = mid;

    if (nel > 2 && nel % 2 != 0)
        ls++;

    /* Copy the elements into tmp arrays. */
    left  = malloc(ls*width);
    right = malloc(rs*width);
    memcpy(left, base, ls*width);
    memcpy(right, base+(ls*width), rs*width);

    merge_sort(left, ls, width, cmp);
    merge_sort(right, rs, width, cmp);

    i = 0;
    j = 0;
    k = 0;
    /* Merge the tmp arrays back into the base array in
     * sorted order. */
    while (i < ls && j < rs) {
        if (cmp(left+(i*width), right+(j*width)) <= 0) {
            memcpy(base+(k*width), left+(i*width), width);
            i++;
        } else {
            memcpy(base+(k*width), right+(j*width), width);
            j++;
        }
        k++;
    }

    /* If left is longer than right copy the remaining elements
     * over */
    while (i < ls) {
        memcpy(base+(k*width), left+(i*width), width);
        i++;
        k++;
    }

    /* If right is longer than right copy the remaining elements
     * over */
    while (j < rs) {
        memcpy(base+(k*width), right+(j*width), width);
        j++;
        k++;
    }

    free(right);
    free(left);
}

The key to making this a stable sort is the <= comparison. If this was only < then elements that appear earlier in the unsorted array will be placed at the end of the sorted array.

Mergesort utilizes temporary arrays for splitting each input array into sub arrays. The temporary arrays are mallocd to avoid running out of stack space. This is a generic implementation and the size of each element or it’s type isn’t known at compile time. Meaning, we have no way to know how much memory would be needed and if it would exceed the stack.

This could be optimized by moving the malloc and memcpy for the right side to after the recursive call to sort the left side. This won’t remove the malloc but it will prevent unused memory from being allocated while the algorithm isn’t using that subarray. The malloc and memcpy calls were all done together for clarity.

Introduction#

The Algorithm Explained#

Introduction

The Algorithm Explained