Timsort vs some others

[Xinok]

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.