Re: [Caml-list] An interesting sorting algorithm for list

[Van Chan Ngo <chan.ngo2203@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1921 bytes --]

Hi,

It sounds interesting. However, I suppose they have the same worst-case
complexity O(nlogn).
Could we formally have the average complexity?

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%
>

[-- Attachment #2: Type: text/html, Size: 2475 bytes --]