On Tue, May 1, 2012 at 10:51 AM, Terry Reedy <tjre...@udel.edu> wrote:
> 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/<http://stromberg.dnsalias.org/%7Estrombrg/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). > Yeah, I know, but thanks for making sure I did. Timsort is a quite impressive algorithm. I suspect that the "sorting a mostly-sorted list in near-linear time" attribute of Timsort tends to encourage sorting in a loop though. Usually sorting inside a loop gives a slow algorithm, even with something as nice as Timsort.
-- http://mail.python.org/mailman/listinfo/python-list
