[Python-Dev] timsort for jython

[Tim Peters]

[Finn Bock]
> ...
> The old sorting code in jython was the 1.5 code from CPython with a
> quicksort implementaion also inspired by Tim Peters.

The sad thing is, that was a very good quicksort -- I thought I was done
when I wrote that <wink>.

> Switching to timsort is obviously a nobrainer for us.

Thanks for sharing this!  Made my day <smile>.  I noted in the Jython patch
that you should see a nice speedup by nuking the assert() calls once you're
confident in the port; Java is checking out-of-bound array indices for you,
and that's largely what the asserts are guarding against in the C
implementation.

> You also don't need to hold back on giving stability garanties in the
> documentation for jython's sake.

I didn't <wink>.  Stability doesn't come free, and for all I know, in
another 3 years a method will be discovered that's 3x faster but not stable.
For example, Splaysort is (as an email correspondent reminded me) provably
adaptive to all known measures of presortedness, but when I looked at the
code it "was obvious" that it wouldn't be competitive on random data; it
also requires two pointers per list element.  In coming years, researchers
may well dream up quicker ways to get the same goodness, but Splaysort isn't
stable, and very few fast algorithms are.  So I don't want to hobble future
implementations by holding Python to promises I don't care much about.
OTOH, I do expect that once code relies on stability, we'll have about as
much chance of taking that away as getting rid of list.append().