Sort comparison

[Terry Reedy]

On 5/1/2012 1:25 AM, Dan Stromberg wrote:

> Anyway, here's the comparison, with code and graph:
> http://stromberg.dnsalias.org/~strombrg/sort-comparison/
>
> (It's done in Pure python and Cython, with a little m4).
>
> Interesting, BTW, that an unstable quicksort in Cython was approaching
> timsort as a C extension module in performance, even though timsort in
> Cython wasn't that performant.  It makes one wonder if a highly
> optimized quicksort as a C extension module wouldn't outperform timsort
> in the standard library.

Timsort is not only stable, but, by design, it is faster than quicksort 
for various structured data patterns, many of which are realistic in 
practice. For instance, you append k unordered items to n already sorted 
items, where k << n, so that k*log(k) is on the order of n. Timsort 
discovers the initial run of n sorted items, sorts the k items, and then 
merges. The practical time is O(n). Ditto for sorting an already sorted 
file in the reverse direction (timsort does an O(n) list reverse).

-- 
Terry Jan Reedy