Hello,

Here is an algorithm I found nice to sort lists.  It is in O(n ln(k))
where n is the size and k the number of changes of direction in the list.

for [ 1; 5; 10; 15; 20; 10; 2; 3; 5; 7], k = 3.

This implementation is a stable sort.

It is "almost" as fast as List.sort in the bad cases (Random lists)
(when k ~ n) and can be much faster if k is small as expected...

A challenge: find a similar algorithm, for lists, that is always
faster than List.sort ... I have tried a lot and I was always 5% slower
on the bas cases ... (Try to remain stable)

Enjoy,
Christophe

PS: the benchmark:

Correctness test passed
Stability test passed
Random lists:
          random: tf = 1.53, tg = 1.56, factor = 0.98x, gain = -2.33%
    random small: tf = 1.37, tg = 1.44, factor = 0.95x, gain = -4.88%
Worst cases:
          worst1: tf = 1.31, tg = 1.38, factor = 0.95x, gain = -5.18%
          worst2: tf = 1.32, tg = 1.36, factor = 0.98x, gain = -2.49%
Sorted (partially) lists:
          sorted: tf = 1.28, tg = 0.01, factor = 97.21x, gain = 98.97%
        reversed: tf = 1.31, tg = 0.17, factor = 7.76x, gain = 87.11%
      sorted@rev: tf = 1.33, tg = 0.37, factor = 3.60x, gain = 72.23%
      rev@sorted: tf = 1.30, tg = 0.38, factor = 3.44x, gain = 70.94%
Shuffled lists (permute k times 2 elements in a sorted list):
      shuffle 10: tf = 1.35, tg = 0.80, factor = 1.68x, gain = 40.64%
     shuffle 100: tf = 1.36, tg = 1.07, factor = 1.27x, gain = 21.56%
    shuffle 1000: tf = 1.38, tg = 1.20, factor = 1.15x, gain = 13.17%
   shuffle 10000: tf = 1.41, tg = 1.25, factor = 1.13x, gain = 11.45%