Stable sort algorithms are slower than unstable sorts. As an example golang uses O(n*log(n)*log(n)) calls to swap elements.
If our goal is to preserve the original order of the elements, why not just number them all (O(n)) then do an unstable sort (O(n*log(n))) using the original index to resolve instances where comparisons are equal.
This seems faster.
i.e. O(n) + O(n*log(n)) < O(n*log(n)*log(n))
Is this correct? Are there any reasons to prefer a stable sort?
Except for cache effects, stable sorts are generally faster than unstable sorts when they are allowed to use extra memory.
The stable sort you link to from golang does not use extra space, so it has to use a slower algorithm. When it's important not to use extra memory, unstable sorts are used instead, because they're almost as fast in most cases and don't require it.
If you have to allocate extra memory for indexes, though, then you might as well use a fast stable sort instead. There are lots of ways to do it in O(N log N) time using the same amount of extra space.
Intro sort (quick sort + heap sort so worst case time complexity is O(n log(n)) on two arrays (original data + indexes to original data) will take longer than merge sort (on a single array), which wouldn't need to sort original data + an array of indexes.
Unstable quicksort is only about 15% faster than merge sort. Sorting two arrays at the same time would make it slower than merge sort. The main disadvantage of merge sort is that it uses a second array. On a processor with 16 registers, such as X86 in 64 bit mode, a 4-way merge sort is about as fast as quicksort.
