Merge Sort: A Fast, Stable, Tried and True O(nlogn) Algorithm

mgcadmin 24-12-2021

Merge Sort

Everybody has their favorite algorithms, and merge sort happens to be one of  mine. It's also one of the definitive "Divide and Conquer" algorithms. There is a certain elegance to merge sort, and unlike Quicksort, it is a stable sorting algorithm. This means that when sorting records with identical keys, the order of those records is preserved. 

Of course all things have a downsize, and one downside to merge sort is that it requires O(n) additional space as it is not an in-place sort. There are two fundamentally different approaches to implementing merge sort: top down merge sort which is a recursive divide and conquer algorithm, and Bottom Up Merge sort which is an iterative algorithm. In todays post I'm going to explain the both methods as they apply to sorting arrays. 

How it works

As stated above Merge sort is a divide and conquer algorithm. It works by recursively halving the input array into smaller and smaller pieces until it is comprised of singlets, as a single item is itsself sorted. There are two approaches to mergesort, the naiive approach, and the implicit approach. 

 Pseudocode for the naiive approach looks like this:

mergesort(array):
let front be an array
let back be an array
let result be an array
if (array.length <= 1) 
   return
for (i = 0 to array.length/2)
copy(array[i] to front[i])
for (j = array.length/2 to array.length)
copy(array[j] to back[j])
mergesort(front)
mergesort(back)
merge(front, back, result)
return result

Pseudocode for the implicit merge sort algorithm looks like this:

mergesort(array, left, right):
if (right - left <= 1) 
  return
middle = right+left / 2
mergesort(array, left, middle)
mergesort(array, middle, right)
merge(array, workarray, left, middle, right)

The naiive approach proceeds by the actual splitting of the array into two other arrays, copying the values from the input array into two work arrays (front and back) and then in the merge function, copying the data from the two work arrays to the result array. While straight forward and illustrative of how the algorithm works, this approach is inefficient because the large amount of copying of data taking place. The second method passes array boundaries as its parameter, leaving all data copying to be done in the merge phase, creating a far more efficient implementation. This is the method we will be using in this article.

The Sorting Phase (Divide)

The sorting phase of mergesort is a recursive function used to set the array boundary delimiters so the merge function knows which slices of the array to work on. It's a pretty straight forward process that has a pretty much 1-to-1 translation of its pseudocode.

void mergesort(int a[], int aux[], int l, int r) {
     if (r - l <= 1)
         return;
     int m = (l+r)/2;
     mergesort(a, aux, l, m);
     mergesort(a, aux, m, r);
     merge(a, aux, l, m, r);
}

void mergesort(int a[], int l, int r) {
    int *aux = new int[r-l+1];
    mergesort(a, aux, l, r);
}

The Merge Phase (Conquer)

Merging is a fundamental concept not just to sorting, but to data processing in general. As such there are many, many ways to write a merge function. The following method makes first checks if either of the two arrays has been exhausted, and if so takes the element from the non exhausted array. Otherwise, on each iteration we choose the smaller element of the two choices until both arrays have been consumed, leaving us with one sorted slice.

void merge(int a[], int aux[], int l , int m, int r) {
      for (int k = l; k < r; k++)
         aux[k] = a[k];
     for (int i = l, j = m, k = l; k < r; k++) {
         if (i == m) { a[k] = aux[j++]; continue; }
         if (j == r) { a[k] = aux[i++]; continue; }
         a[k] = (aux[j] > aux[i]) ? aux[i++]:aux[j++]; 
     }
}

 

Optimizing Top Down Merge Sort

I seperated the recursive function and the merge operation into two seperate functions for the ease of explaining the two phases and illustrating its divide and conquer approach, however we can combine them into one function which will give us a slight speed increase, as well as aid in keeping the size of the call stack down. We can also use the "small sub array insertion sort" optimization, where we set a thresh hold that switches merge sort to insertion sort when the array hits a certain size. With these two modifications in place our final algorithm looks like this:

void insertionsort(int a[], int l, int r) {
    for (int i = l; i < r; i++) {
        int j = i, v = a[j];
        while (j > l && a[j - 1] > v) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = v;
    }
}

void mergesort(int a[], int aux[], int l, int r) {
    if (r - l < 10) {
        insertionsort(a, l, r);
        return;
    }
    int m = (l+r)/2;
    mergesort(a, aux, l, m);
    mergesort(a, aux, m, r);
    for (int k = l; k < r; k++)
        aux[k] = a[k];
    for (int i = l, j = m, k = l; k < r; k++) {
        if (i == m) { a[k] = aux[j++]; continue; }
        if (j == r) { a[k] = aux[i++]; continue; }
        a[k] = (aux[j] > aux[i]) ? aux[i++]:aux[j++]; 
    }
}

void mergesort(int a[], int l, int r) {
    int *aux = new int[r-l+1];
    mergesort(a, aux, l, r);
}

 

Bottom Up Mergesort

Bottom up mergesort is a purely iterartive implementation that does away with the recursive step of breaking the list into smaller and smaller sub lists, and simply starts with subarrays of size 1.

void mergesort(int a[], int l, int r) {
    int n = r-l;
    int *aux = new int[r-l];
    for (int len = 1; len < n; len = 2*len) {
        for (int width = l; width < r-len; width += 2*len) {
            int left = width, mid = left+len, right = min(left+len+len, n);
            merge(a, aux, left, mid, right);
        }
    }
}

Another variant of bottom up mergesort, called tiled mergesort use the optimization from above of using insertion sort on small arrays. This time however, we start with insertion sort, and then proceed by mergeing slices of size N, where N is the size of the slice we chose to insertion sort.

void mergesort(int a[], int l, int r) {
    int n = r-l;
    int *aux = new int[r-l];
    int slice_size = 8;
    for (int i = l; i < r; i += slice_size) {
        insertionsort(a, i, min(r, i+slice_size));
    }
    for (int len = slice_size; len < n; len = 2*len) {
        for (int width = l; width < r-len; width += 2*len) {
            int left = width, mid = left+len, right = min(left+len+len, n);
            merge(a, aux, left, mid, right);
        }
    }
}

 

---