Алгоритмы сортировки

[metaclass]

Народ развлекается забавной задачкой про stl и quicksort.
Заглянув в исходники stl, я понял, что называть это "обычным quicksort" это какое-то явное издевательство.
И еще оказалось, что обычный quicksort из дельфи работает раза в два медленнее чем этот хитрый std::sort, хотя я думаю, кроме всех оптимизаций, там еще косвенный вызов функции сравнения в дельфи свою лепту вносит.

Comments

[x-a-e-p.livejournal.com]

Хотя бы то, что сложность сортировки гарантированно должна быть(по стандарту) O(N*log(N)), говорит о том, что это не quicksort.

[x-a-e-p.livejournal.com]

Ну я скорее спорил насчёт quicksort

[tonal.myopenid.com (from livejournal.com)]

по сравнению с делфовой версией там вроде только 2 заметных улучшения:
1. Инлайнинг функции сравнения
2. Сортировка коротких последовательностей с помощью вставок.
Остальное мелкие оптимизации - типа немного разных алгоритмов для граничных и внутренних подпоследовательностей.

Кроме 1-го всё можно без труда повторить на дельфе для конкретного типа.