Timsort vs some others

[Joseph Rushton Wakeling]

On 12/18/2012 07:52 AM, Xinok wrote:
> While Smoothsort may be mathematically sound, it simply doesn't translate well
> to computer hardware. It's a variant of heap sort which requires a great deal of
> random access, whereas Timsort is a variant of merge sort which is largely
> sequential and benefits from the CPU cache. Furthermore, the Leonardo heap is
> much more computationally expensive than a typical binary or ternary heap.

... but I would guess that given the O(1) memory requirements it probably scales 
much better to sorting really, really large data, no?

That was surely a much, much bigger issue back in 1981 when Dijkstra proposed 
it, but still has a place today.