[Python-Dev] Sorting

[Tim Peters]

[MAL]
> Here's the result for AMD Athlon 1.2GHz/Linux/gcc:
>
> Python/Tim-Python> ./python -O Lib/test/sortperf.py 15 20 1
>   i    2**i  *sort  \sort  /sort  3sort  +sort  ~sort  =sort  !sort
> 15   32768   0.07   0.00   0.01   0.09   0.01   0.03   0.01   0.08
> 16   65536   0.18   0.02   0.02   0.19   0.03   0.07   0.02   0.20
> 17  131072   0.43   0.05   0.04   0.46   0.05   0.18   0.05   0.48
> 18  262144   0.99   0.09   0.10   1.04   0.13   0.40   0.09   1.11
> 19  524288   2.23   0.19   0.21   2.32   0.24   0.83   0.20   2.46
> 20 1048576   4.96   0.40   0.40   5.41   0.47   1.72   0.40   5.46
>
> without patch:
>
> Python/Tim-Python> ./python -O Lib/test/sortperf.py 15 20 1
>   i    2**i  *sort  \sort  /sort  3sort  +sort  ~sort  =sort  !sort
> 15   32768   0.08   0.01   0.01   0.09   0.01   0.03   0.00   0.09
> 16   65536   0.20   0.02   0.01   0.20   0.03   0.07   0.02   0.20
> 17  131072   0.46   0.06   0.02   0.45   0.05   0.20   0.04   0.49
> 18  262144   0.99   0.09   0.10   1.09   0.11   0.40   0.12   1.12
> 19  524288   2.33   0.20   0.20   2.30   0.24   0.83   0.19   2.47
> 20 1048576   4.89   0.40   0.41   5.37   0.48   1.71   0.38   6.22

I assume you didn't read the instructions in the patch description:

    http://www.python.org/sf/587076

The patch doesn't change anything about how list.sort() works, so what
you've shown us is the timing variance on your box across two identical
runs.  To time the new routine, you need to (temporarily) change L.sort() to
L.msort() in sortperf.py's doit() function.  It's a one-character change,
but an important one <wink>.