Logged In: YES 
user_id=250749

The following results are from your original patch (the n
column dropped for better SF display).

System 1:
Athlon 1.4Ghz, 256MB PC2100 RAM, OS2 v4 FixPack 12, EMX 0.9d
Fix 4

gcc 2.8.1 -O2
samplesort
 i  *sort  \sort  /sort  3sort  +sort  ~sort  =sort  !sort
15   0.07   0.01   0.01   0.07   0.01   0.03   0.02   0.08
16   0.18   0.02   0.01   0.18   0.02   0.08   0.01   0.20
17   0.41   0.04   0.04   0.43   0.05   0.18   0.04   0.46
18   0.93   0.09   0.10   1.00   0.10   0.39   0.10   1.05
19   2.08   0.18   0.20   2.34   0.23   0.81   0.20   2.36
20   4.69   0.37   0.40   5.02   0.47   1.68   0.40   5.28

timsort
 i  *sort  \sort  /sort  3sort  +sort  ~sort  =sort  !sort
15   0.06   0.01   0.01   0.01   0.01   0.03   0.01   0.02
16   0.15   0.03   0.01   0.02   0.02   0.06   0.02   0.04
17   0.37   0.04   0.05   0.04   0.05   0.13   0.05   0.10
18   0.88   0.10   0.09   0.10   0.10   0.28   0.10   0.19
19   1.97   0.20   0.18   0.21   0.21   0.58   0.20   0.39
20   4.40   0.41   0.40   0.42   0.40   1.21   0.40   0.81

gcc 2.95.2 -O3
samplesort
 i  *sort  \sort  /sort  3sort  +sort  ~sort  =sort  !sort
15   0.07   0.01   0.00   0.07   0.01   0.03   0.00   0.08
16   0.17   0.01   0.03   0.17   0.02   0.09   0.02   0.19
17   0.42   0.05   0.04   0.46   0.06   0.18   0.05   0.45
18   0.99   0.09   0.09   1.05   0.12   0.40   0.09   1.05
19   2.09   0.18   0.21   2.18   0.23   0.84   0.20   2.45
20   4.73   0.39   0.41   5.13   0.47   1.70   0.40   5.38

timsort
 i  *sort  \sort  /sort  3sort  +sort  ~sort  =sort  !sort
15   0.10   0.01   0.01   0.01   0.01   0.04   0.01   0.01
16   0.18   0.02   0.01   0.03   0.02   0.07   0.03   0.03
17   0.37   0.06   0.05   0.04   0.05   0.14   0.04   0.09
18   0.91   0.10   0.10   0.10   0.10   0.27   0.09   0.20
19   1.97   0.21   0.21   0.20   0.20   0.59   0.19   0.40
20   4.31   0.44   0.40   0.44   0.40   1.21   0.40   0.82


System 2:
P5-166 SMP (2 CPU), 64MB 60ns FPM RAM, FreeBSD 4.4-RELEASE
with a 
  patch to re-enable CPU L1 caches (SMP BIOS issue)
gcc 2.95.3 -O3
samplesort
 i  *sort  \sort  /sort  3sort  +sort  ~sort  =sort  !sort
15   0.73   0.06   0.05   0.74   0.07   0.23   0.05   0.77
16   1.60   0.12   0.12   1.66   0.13   0.48   0.12   1.71
17   3.54   0.26   0.24   3.55   0.27   1.05   0.25   3.74
18   7.63   0.52   0.51   7.73   0.58   2.12   0.50   8.05
19  16.38   1.04   1.01  17.03   1.15   4.28   1.01  17.17
20  34.94   2.09   2.02  35.04   2.37   8.62   2.02  36.58

timsort
 i  *sort  \sort  /sort  3sort  +sort  ~sort  =sort  !sort
15   0.74   0.05   0.06   0.06   0.06   0.32   0.06   0.12
16   1.64   0.12   0.12   0.12   0.12   0.65   0.12   0.26
17   3.62   0.25   0.25   0.27   0.26   1.32   0.25   0.52
18   7.78   0.51   0.50   0.53   0.52   2.69   0.50   1.06
19  16.76   1.03   1.01   1.09   1.04   5.46   1.01   2.12
20  35.93   2.09   2.02   2.14   2.09  11.05   2.04   4.38


System 3:
486DX4-100, 32MB 60ns FPM RAM, FreeBSD 4.4-RELEASE
gcc 2.95.3 -O3
samplesort
 i  *sort  \sort  /sort  3sort  +sort  ~sort  =sort  !sort
15   2.62   0.21   0.21   2.61   0.24   0.83   0.21   2.71
16   5.73   0.45   0.44   5.75   0.48   1.71   0.44   5.94
17  12.46   0.90   0.88  12.34   1.00   3.70   0.89  13.00
18  27.15   1.82   1.80  27.12   2.17   7.59   1.80  28.10
19  57.22   3.77   3.68  59.52   4.41  15.40   3.66  59.62
20 126.80   7.96   7.80 127.63   9.58  32.72   7.46 134.45

timsort
 i  *sort  \sort  /sort  3sort  +sort  ~sort  =sort  !sort
15   2.52   0.21   0.20   0.20   0.20   1.05   0.20   0.42
16   5.49   0.45   0.41   0.43   0.44   2.13   0.43   0.90
17  12.15   0.88   0.84   0.85   0.88   4.34   0.88   1.83
18  26.11   1.82   1.74   1.84   1.81   8.70   1.74   3.67
19  56.34   3.67   3.55   3.80   3.67  17.84   3.53   7.48
20 121.95   7.89   7.37   8.24   7.98  39.38   7.44  16.83


NOTES:

System 2 is just starting to swap in the i=20 case.

System 3 starts to swap at i=18; at i=19, process:resident
size is 2:1; at i=20, process:resident size is a bit over 4:1.