[ComputerGuru]

Of course in the real world for problems where sorting is actually the bottleneck and not just something you want not to kill your app's performance, you end up with things like timsort that destroy all these in practice.

[bjoli]

I'd say it's the other way around: you use whatever your language provides as default (which is probably something like Timsort) until it becomes a bottleneck and then you analyse the data and write something that is specific to your use case that will blow Timsort out of the water.

Timsort is your first choice.

[btilly]

In practice this boils down to, "you use whatever your language provides".

If sorting became a bottleneck, I'd literally look at every possible approach to speed it up that I could find before considering improving the sorting algorithm. Starting with trying to figure out how to throw around less data while trying to solve the problem.

[nift]

As someone who has spend a great deal of time on sorting algorithms when I was in academia ( even published one) I completely agree with this sentiment. Sorting algorithms are tricky to get right and there is a lot of edge cases, so even when you (think) you know what you are doing you still get it wrong. Been there many times and it always causes some frustration.

Do you really want your business critical sorting rely on something that only might work?

Sorting algorithms are like crypto, don't roll your own if you can avoid it.

[bjoli]

For a problem i faced I ended up being able to produce very small chunks of already sorted data and using the merge part of the stable sort algorithm (it was provided).

Not only that, I ended up being able to do it lazily making the user experience much better.

[btilly]

And I have been forced to write sorting algorithms from scratch as well. But it was truly a last resort. In my case I had to work with data that literally did not fit in uncompressed form on the computer that I had to work with. So I had to write a disk sort where data as kept in compressed form. (I used merge sort for this.)

However the fact that sometimes we are forced to our last resort doesn't change the fact that we should be aware that it really is a last resort.

[bjourne]

Is there any evidence of timsort being superior in practice? I've been looking for benchmarks but on synthetic ones with randomized data, both mergesort and quicksort handily beats timsort. The belief about timsort's superiority seem to me to be more about Tim Peters being a very well-respected developer than performance data.

[pjscott]

On completely random data, Timsort is just a mergesort with some extra bookkeeping. Its advantage is on arrays that have sorted subarrays of non-trivial size, which is often the case with real data.

[civility]

Also no mention of introsort (C++ std::sort), where it uses insertion sort for small arrays, detects if it's fallen too far towards O(n^2) of quicksort, and punts to heapsort when it needs to.

[hinkley]

You can pry my stable sort algorithms out of my cold, dead hands.

[civility]

Heh, I think stable sorts are great. However, you don't always need one, and you do pay a little bit for it.

[jfoutz]

Add the factors to the sort key? Every sort is stable if you have some vague ideas about what to sort on.

[hinkley]

What?