dual-pivot quicksort

[valyard]

Что я могу сказать, обычный школьный квиксорт с массивами в 3 раза медленнее у меня получается. Оптимизированный без создания и объединения толпы новых массивов я не помню как делать и лень.
AS3, 50000 элементов. По пути был немного удивлен тем, что Array.sort в 12 раз медленнее.

Ничего больше особо не знаю об алгоритмах сортировки с университета, про оригинальность сказать не могу, но работает же. Сохраню чтоб не забыть.

Хотелось бы еще тестов и мыслей математиков получше чем я.

[GigaOM]

Ждал как минимум код с коментариями… Вполне бы можно оформить было ссылкой, а не топиком.

[sylvio]

Оригинал здесь

[max7]

У меня получились такие отношения количеств (приблизительно) на рандомных массивах до миллиона чисел:

сравнений «dual-pivot quicksort» к «classic quicksort»: ~1 ~1.05;
обменов «dual-pivot quicksort» к «classic quicksort»: ~2 ~2.5;
вызовов «classic quicksort» к «dual-pivot quicksort»: ~7.5 ~9.5.

Так что есть над чем подумать.

[max7]

А вот если привести оба алгоритма к одному виду, то количество вызовов вызовов «classic quicksort» к «dual-pivot quicksort» будет ~1.5. В этом случае преимущества приведённого алгоритма неясны :(

[kronos]

Портировал в Rubinius, тестирую. Выглядит неплохо :)

[Maxime]

Похоже это частный случай вот этого открытого патента.