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%