[Python-Dev] Sorting

[M.-A. Lemburg]

Tim Peters wrote:
> Apart from fine-tuning and rewriting the doc file, I think the mergesort is
> done.  I'm confident that if any bugs remain, I haven't seen them <wink>.  A
> patch against current CVS listobject.c is here:
> 
>     http://www.python.org/sf/587076
> 
> Simple instructions for timing exactly the same data I've posted times
> against are in the patch description (you already have sortperf.py -- it's
> in Lib/test).  This patch doesn't replace samplesort, it adds a new .msort()
> method, to make comparative timings easier.  It also adds an .hsort() method
> for weak heapsort, because I forgot to delete that code after I gave up on
> it <wink>.
> 
> X-platform samplesort timings are interesting as well as samplesort versus
> mergesort timings.  Timings against "real life" sort jobs are especially
> interesting.  Attaching results to the bug report sounds like a good idea to
> me, so we get a coherent record in one place.
> 
> Thanks in advance!

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

-- 
Marc-Andre Lemburg
CEO eGenix.com Software GmbH
_______________________________________________________________________
eGenix.com -- Makers of the Python mx Extensions: mxDateTime,mxODBC,...
Python Consulting:                               http://www.egenix.com/
Python Software:                    http://www.egenix.com/files/python/