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
--
http://mail.python.org/mailman/listinfo/python-list
