Sort comparison

[Dan Stromberg]

On Tue, May 1, 2012 at 10:51 AM, Terry Reedy <tjreedy at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20120501/0d2d165f/attachment-0001.html>