This blog post discusses stable sort implementations in various languages, and it also presents a non-recursive, fast and compact mergesort implementation in C++. The implementation runs the original mergesort algorithm in an iterative way with some optimizations, so it is stable.
Please note that C++ STL has a stable sort built in: std::stable_sort in #include <algorithm>. If it's OK to use STL in your C++ code, use that, and you won't need any custom code from this blog post.
About compactness: when compiled statically with GCC 4.1.2 (g++ -fno-rtti -fno-exceptions -s -O2 -static) for i386, the mergesort in this blog post produces an executable 4084 bytes smaller than with std::stable_sort.
About speed: between 10% and 16% faster than std::stable_sort, see speed measurements below.
The fast, non-recursive, stable sort implementation in C++
It's a non-recursive, stable mergesort implementation, with O(n*log(n)) worst-case speed.
#include <sys/types.h>
// Stable, non-recursive mergesort algorithm. Sort a[:n], using temporary
// space of size n starting at tmp. (Please note that mergesort Algorithm
// 5.2.4N and Algorithm 5.2.4S from Knuth's TAOCP are not stable. Please
// note that most implementations of mergesort found online are recursive,
// thus slower.)
//
// by pts@fazekas.hu at Sun Aug 18 19:23:36 CEST 2013
template <typename T, typename IsLess>
void mergesort(T *a, size_t n, T *tmp, IsLess is_less) {
for (size_t f = 1; f < n; f += 2) { // Unfold the first pass for speedup.
if (is_less(a[f], a[f - 1])) {
T t = a[f];
a[f] = a[f - 1];
a[f - 1] = t;
}
}
bool s = false;
for (size_t p = 2; p != 0 && p < n; p <<= 1, s = !s) {
// Now all sublists of p are already sorted.
T *z = tmp;
for (size_t i = 0; i < n; i += p << 1) {
T *x = a + i;
T *y = x + p;
size_t xn = p < n - i ? p : n - i;
size_t yn = (p << 1) < n - i ? p : p < n - i ? n - p - i : 0;
if (xn > 0 && yn > 0 &&
is_less(*y, x[xn - 1])) { // Optimization (S), Java 1.6 also has it.
for (;;) {
if (is_less(*y, *x)) {
*z++ = *y++;
if (--yn == 0) break;
} else {
*z++ = *x++;
if (--xn == 0) break;
}
}
}
while (xn > 0) { // Copy from *x first because of (S).
*z++ = *x++;
--xn;
}
while (yn > 0) {
*z++ = *y++;
--yn;
}
}
z = a; a = tmp; tmp = z;
}
if (s) { // Copy from tmp to result.
for (T *x = tmp, *y = a, * const x_end = tmp + n; x != x_end; ++x, ++y) {
*x = *y;
}
}
}
Some convenience functions to call it:
// Stable, non-recursive mergesort.
// To sort vector `a', call mergesort(a.data(), a.data() + a.size(), is_less)'
// or use the convenience function below.
template <typename T, typename IsLess>
void mergesort(T *a, T *a_end, IsLess is_less) {
const size_t n = a_end - a;
if (n < 2) return;
// Creating ptr_deleter so tmp will be deleted even if is_less or
// mergesort throws an exception.
struct ptr_deleter {
ptr_deleter(T *p): p_(p) {}
~ptr_deleter() { delete p_; }
T *p_;
} tmp(new T[n]);
mergesort(a, n, tmp.p_, is_less);
}
// Convenience function to sort a range in a vector.
template <typename T, typename IsLess>
// Doesn't match:
//static void mergesort(const typename std::vector<T>::iterator &begin,
// const typename std::vector<T>::iterator &end,
//static void mergesort(const typename T::iterator &begin,
// const typename T::iterator &end,
void mergesort(const T &begin, const T &end, IsLess is_less) {
mergesort(&*begin, &*end, is_less);
}
// Stable, non-recursive mergesort.
// Resizes v to double size temporarily, and then changes it back. Memory may
// be wasted in b after the call because of that.
template <typename T, typename IsLess>
void mergesort_consecutive(std::vector<T> *v, IsLess is_less) {
const size_t n = v->size();
if (n < 2) return;
v->resize(n << 1); // Allocate temporary space.
mergesort(v->data(), n, v->data() + n, is_less);
v->resize(n);
}
Example invocation:
inline bool int_mask_less(int a, int b) {
return (a & 15) < (b & 15);
}
...
std::vector<int> a;
...
mergesort(a.begin(), a.end(), int_mask_less);
A slow, non-recursive stable sort implementation in C++
If you don't care about speed, an insertion sort would do: it's simple (short), stable and non-recursive. Unfortunately it's slow: O(n2) in worst case and average.
// Insertion sort: stable but slow (O(n^2)). Use mergesort instead if you need
// a stable sort.
template <typename T, typename IsLess>
static void insertion_sort(T *a, T *a_end, IsLess is_less) {
const size_t n = a_end - a;
for (size_t i = 1; i < n; ++i) {
if (is_less(a[i], a[i - 1])) {
T t = a[i];
size_t j = i - 1; // TODO: Use pointers instead of indexes.
while (j > 0 && is_less(t, a[j - 1])) {
--j;
}
for (size_t k = i; k > j; --k) {
a[k] = a[k - 1];
}
a[j] = t;
}
}
}
// Convenience function to sort a range in a vector.
template <typename T, typename IsLess>
static void insertion_sort(const T &begin, const T &end, IsLess is_less) {
insertion_sort(&*begin, &*end, is_less);
}
C++ stable sort speed measurements
10000 random int vectors (of random size smaller than 16384) were sorted in place in a C++ program running on Linux 2.6.35 running on an Intel Core 2 Duo CPU T6600 @ 2.20GHz. The total user time was measured, including the sort, the running of std::stable_sort, and the verification of the sort output (i.e. comparing it to the output of std::stable_sort. The insmax parameter below indicates the size of the sublists with were sorted using insertion sort before running the mergesort (the implementation above uses insmax=2, which is implemented in the Unfold... loop).
The raw time measurement results:
mask= 15 insmax= 1 18.805s
mask= 15 insmax= 2 17.337s
mask= 15 insmax= 4 17.109s
mask= 15 insmax= 8 17.133s
mask= 15 insmax=16 17.153s
mask= 15 insmax=32 17.325s
mask= 15 insmax=64 18.221s
mask= 15 std::stable_sort 19.401s
mask= 15 insertion_sort 500.83s
mask=255 insmax= 1 19.349s
mask=255 insmax= 2 18.357s
mask=255 insmax= 4 18.493s
mask=255 insmax= 8 18.585s
mask=255 insmax=16 18.741s
mask=255 insmax=32 19.081s
mask=255 insmax=64 20.061s
mask=255 std::stable_sort 21.965s
mask=255 insertion_sort 530.27s
It looks like that the mergesort algorithm proposed in this blog post (insmax=2 in the measurements above) is between 10% and 16% faster than std::stable_sort. It looks like that increasing insmax from 2 to 8 could yield an additional 1.18% speed increase.
Stable sort in other programming languages
Other stable sorting algorithms
Heapsort and quicksort are not stable. Some variations of mergesort (such as Algorithm 5.2.4N and Algorithm 5.2.4S in The Art of Computer programming, Volume 3 by Knuth) are not stable.
This page lists stable sorting algorithms known to mankind. Be careful with the implementations though: even if the algorithm itself is stable, some optimized, otherwise modified or buggy implementations might not be. The algorithms are:
- O(n*log(n)), stable, comparison-based: mergesort, cascade merge sort, oscillating merge sort.
- O(n2), stable, comparison-based: bubble sort, cocktail sort, insertion sort, binary insertion sort (where the insertion index is found using binary search), gnome sort, library sort, odd-even sort.
- O(n2), stable, not comparison-based: bucket sort, proxmap sort.
- faster than O(n2), stable, not comparison-based: counting sort, pigeonhole sort, radix sort.
So it looks like that we don't know of an alternative of mergesort for comparison-based sorting in O(n*log(n)) time, the others above are slower. Maybe Edsger Dijkstra[citation needed] can come up with an alternative.
