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++;
}
}
}
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);
}
And of course, you could still make use of other optimizations such as small subarray insertion sorting, removing recursion or both.
So now you know how std::stable_sort can still sort performantly even when heap space is at a minimum. Happy hacking!
