On Tuesday, 18 December 2012 at 15:27:07 UTC, Joseph Rushton
Wakeling wrote:
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?
Heap sort actually performs really well if the entirety of the
data is small enough to fit into the CPU cache. But on larger
data sets, heap sort is jumping all over the place resulting in a
significant number of cache misses. When a block of memory is
stored in cache, it doesn't remain there for long and very little
work is done on it when it is cached. (I mention heap sort
because the leonardo heap of smoothsort is still very
computationally expensive)
Although merge sort is O(n), it's sequential nature results in
far fewer cache misses. There are three blocks of memory being
operated on at anytime: the two blocks to be merged, and a
temporary buffer to store the merged elements. Three (or four)
small pieces of memory can be sorted in the cache without any
cache misses. Furthermore, thanks to the divide-and-conquer
nature of merge sort, fairly large sublists can be sorted
entirely in the CPU cache; this is even more so if you
parallelize on a multi-core CPU which has a dedicated L1 cache
for each CPU. Merge sort can be further optimized by using
insertion sort on small sublists... which happens entirely in the
CPU cache...
Another way to put it, merge sort is an ideal algorithm for
sorting linked lists, and it was even practical for sorting large
lists stored on tape drives.
Quick sort is a sequential sorting algorithm with O(log n) space
complexity which is likely the reason it outperforms merge sort
in most cases, albeit not being stable.
