In-place Merge Sorting

mgcadmin 22-03-2023

If you're familiar with the C++ Standard Library, and the C++ Standards at large, you know that certain performance requirements are laid out for the algorithms it contains. The built in sorting algorithms are no exception.

It is well known that std::sort is the reference implementation of Introspective Sort, designed specifically for STL. std::stable_sort does not name a specific algorithm that should be implemented, but it is worded in a way as to strongly suggest using a merge sort algorithm. Closer reading however specifies that if the O(N) additional memory required for merge sort is not available, it should fall back to a stable sorting algorithm with worst case time complexity of O(n log^2 n).

So what algorithm meets those requirements?

In Place Merge Sort

Standard merge sort makes the trade off of using extra memory in order to run faster. This is good compromise, if you have the memory to spare. Unfortunately, a situation can arise where that may not be possible, and there aren't a whole lot of O(n log n) sorting algorithms, even less that are stable. So, what's the next best thing? What if we could remove the O(n) memory requirement, while still performing few, though not-quite O(n log n) worst case comparisons?

We're going to make use of the shift and insert method to move our elements around in place, a la insertion sort. It turns out that with careful manipulation of our index pointers, merging in place is actually pretty straight forward:

 void merge(int a[], int l, int m, int r) {
    int i = l; int j = m;
    while (i < m && j < r)
    {
        if (a[i] < a[j]) {
            i++;
        } else {
            int v = a[j];
            int p = j;
            while (p > i) {
                a[p] = a[p - 1];
                p--;
            }
            a[p] = v;
            i++;
            j++;
            m++;
        }
    }
} 

It's actually a fairly clever approach, exploiting the fact that when a[i] < a[j], then a[i] is already in place. This allows us to treat the front portion of the array as a "growing" portion of sorted items by incrementing the m pointer as items are added. Items from the unsorted portion of the array are merged into place using simple iterative insertion. The great part about this merge method, is that the sort phase of the algorithm still proceeds as usual:

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

Happy hacking!

 

---