[Python-Dev] Pie-thon benchmarks

[Tim Peters]

[Guido]
>> Ah, but then Dan will just add Karatsuba multiplication to Parrot,
>> too.  And AFAIK, Timsort isn't patented. :-)

[Delaney, Timothy C (Timothy)]
> True. But do you really expect that anyone except Tim could get it
> *right*???

Yup!  I documented the approach in soul-numbing detail.  Last I saw, Perl
had an adaptive mergesort too, and in principle that's the same thing.  The
Python implementation is a lot more long-winded, because it's trying harder
to use less memory and be friendlier to the cache, uses only less-than
instead of Perl's 3-outcome comparison primitive, and tries harder to
minimize wasted comparisons if the data turns out to be random -- but that's
all shallow complication.  The core idea can be explained in less than 50
pages of dense text <wink>.  OK, in less than 50 words:  when one input to a
merge "wins" several times in a row, you can potentially save a ton of
comparisons by skipping ahead.  All the rest is engineering.