[Python-Dev] timsort for jython

[Finn Bock]

Hi,

Here are some numbers for a javaport of the timsort code.

https://sourceforge.net/tracker/index.php?func=detail&aid=590360&group_id=12867&atid=312867

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

Switching to timsort is obviously a nobrainer for us. You also don't 
need to hold back on giving stability garanties in the documentation for 
jython's sake.

All numbers using JDK1.4.1 on Win2K & 1300Mhz AMD. I gave up waiting for 
the i=20 line.

quicksort/insertionsort:

  i  *sort  \sort  /sort  3sort  +sort  %sort  ~sort  =sort  !sort
15   0.66   0.50   0.30   0.29   0.40   0.42   0.32   0.28   2.53
16   1.36   1.10   0.67   0.67   0.94   1.05   0.75   0.60   6.12
17   3.12   2.38   1.47   1.47   1.88   2.12   1.62   1.28  15.43
18   6.52   5.14   3.22   3.22   4.52   5.56   3.35   2.73  36.04
19  14.32  11.07   6.99   6.99   8.71  11.72   7.33   5.86  87.80

timsort:

  i  *sort  \sort  /sort  3sort  +sort  %sort  ~sort  =sort  !sort
15   0.44   0.05   0.03   0.03   0.04   0.06   0.17   0.02   0.06
16   0.82   0.08   0.06   0.07   0.07   0.11   0.32   0.05   0.11
17   1.76   0.18   0.13   0.13   0.13   0.23   0.64   0.11   0.22
18   3.87   0.34   0.26   0.29   0.27   0.49   1.29   0.21   0.45
19   8.91   0.70   0.53   0.54   0.54   1.07   2.62   0.43   0.90


regards,
finn