Hi

On 17-10-02 16:05:25, Van Chan Ngo wrote:
> Hi,
>
> It sounds interesting. However, I suppose they have the same worst-case
> complexity O(nlogn).

Yes sure word case is k=O(n).

> Could we formally have the average complexity?

Yes, O(n log n). It is not too hard to see that lists have k = O(n) in
average. No miracle to hope here. However there are a lot of practical
cases where k is lower in average.

The only fun challenge is to have a O(n ln(k) algorithm that is always faster
than the current merge sort of OCaml ... This is hard because the
merge sort is very well suited for a language like OCaml, that can allocates
memory really fast.

Cheers,
Christophe

> Best,
> -Van Chan
>
>
> On Mon, Oct 2, 2017 at 12:11 AM, Christophe Raffalli <christophe@raffalli.eu>
> wrote:
>
>     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%
>
>