<br><div class="gmail_quote">On Tue, May 1, 2012 at 10:51 AM, Terry Reedy <span dir="ltr"><<a href="mailto:tjreedy@udel.edu" target="_blank">tjreedy@udel.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im">On 5/1/2012 1:25 AM, Dan Stromberg wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Anyway, here's the comparison, with code and graph:<br>
<a href="http://stromberg.dnsalias.org/%7Estrombrg/sort-comparison/" target="_blank">http://stromberg.dnsalias.org/<u></u>~strombrg/sort-comparison/</a><br>
<br>
(It's done in Pure python and Cython, with a little m4).<br>
<br>
Interesting, BTW, that an unstable quicksort in Cython was approaching<br>
timsort as a C extension module in performance, even though timsort in<br>
Cython wasn't that performant.  It makes one wonder if a highly<br>
optimized quicksort as a C extension module wouldn't outperform timsort<br>
in the standard library.<br>
</blockquote>
<br></div>
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).<span class="HOEnZb"><font color="#888888"></font></span><br>
</blockquote><div><br>Yeah, I know, but thanks for making sure I did.<br><br>Timsort is a quite impressive algorithm.<br><br>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.<br>
<br></div></div>