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.
