[Python-Dev] Sorting

[Tim Peters]

FYI, I've been poking at this in the background.  The ~sort regression is
vastly reduced, via removing special-casing and adding more general
adaptivity (if you read the timsort.txt file, the special case for run
lengths within a factor of 2 of each other went away, replaced by a more
intelligent mix of one-pair-at-a-time versus galloping modes).

*sort lost about 1% as a result (one-pair-at-a-time is maximally effective
for *sort, but in a random mix every now again the "switch to the less
efficient (for it) galloping mode" heuristic triggers by blind luck).

There's also a significant systematic regression in timsort's +sort case,
although it remains faster (and much more general) than samplesort's
special-casing of it; also a mix of small regressions and speedups in 3sort.
These are because, to simplify experimenting, I threw out the "copy only the
shorter run" gimmick, always copying the left run instead.  That hurts +sort
systematically, as instead of copying just the 10 oddball elements at the
end, it copies the very long run of N-10 elements instead (and as many as
N-1 temp pointers can be needed, up from N/2).  That's all repairable, it's
just a PITA to do it.

C:\Code\python\PCbuild>python -O sortperf.py 15 20 1
samplesort
 i    2**i  *sort  \sort  /sort  3sort  +sort  ~sort  =sort  !sort
15   32768   0.18   0.01   0.02   0.11   0.01   0.04   0.01   0.11
16   65536   0.24   0.02   0.02   0.25   0.02   0.08   0.02   0.24
17  131072   0.53   0.05   0.04   0.49   0.05   0.18   0.04   0.52
18  262144   1.16   0.09   0.09   1.06   0.12   0.37   0.09   1.14
19  524288   2.53   0.18   0.17   2.30   0.24   0.75   0.17   2.47
20 1048576   5.48   0.37   0.35   5.18   0.45   1.52   0.35   5.35

timsort
 i    2**i  *sort  \sort  /sort  3sort  +sort  ~sort  =sort  !sort
15   32768   0.17   0.01   0.02   0.01   0.01   0.05   0.01   0.02
16   65536   0.24   0.02   0.02   0.02   0.02   0.09   0.02   0.04
17  131072   0.54   0.05   0.04   0.05   0.05   0.19   0.04   0.09
18  262144   1.17   0.09   0.09   0.10   0.10   0.38   0.09   0.18
19  524288   2.56   0.18   0.17   0.20   0.20   0.79   0.17   0.36
20 1048576   5.54   0.37   0.35   0.37   0.41   1.62   0.35   0.73

In short, there's no real "speed argument" against this anymore (as I said
in the first msg of this thread, the ~sort regression was serious -- it's an
important case; turns out galloping is very effective at speeding it too,
provided that dumbass premature special-casing doesn't stop galloping from
trying <wink>).