Описание алгоритмов сортировки и сравнение их производительности

Есть такая репа с сортировками: github.com/Morwenn/cpp-sort

Также стоило бы упомянуть такие сортировки как Boost.Sort и pdqsort, которая используется в Rust: они являются очень быстрыми.

А за бенчмарк спасибо — будет полезная ссылка.

Почему производилось по 20 запусков на тест?
Что за системные глюки наблюдались?
Как измерялось время?
Имеет ли смысл сделать то же самое под Linux?

O-нотация верхний предел его настоящей сложности
для точного и наилучшего используются другие обозначения Θ и Ω(ω)
см Введение в анализ сложности алгоритмов на хабре

Сейджвик как-то в курсе по алгоритмам говорил, что на производительность сильно влияет как хорошо алгоритмы работают с кэшами процессора. Например merge sort хорошо с ними работает, а heap sort наоборот. Поэтому даже с учетом того что merge sort требует больше памяти его предпочитают heap sort.

Heapsort на C++ пишется в 2 строчки:

std::make_heap(l, r);
std::sort_heap(l, r);

Построение кучи требует O(r-l) времени.
Heapsort требует O(1) дополнительной памяти.

Занятно, но ощущение противоречивое…

Во-первых, мне кажется, для одной статьи это слишком большое число алгоритмов. Было бы лучше сгруппировать их в 2-3 группы. Например, по устойчивости (сохранении порядка элементов с одинаковым значением ключа) или по другому критерию.

Во-вторых, не хватает сводной таблички, в которой бы указывались такие характеристики:

1. Устойчивость — сохраняется ли порядок элементов с одинаковыми значениями ключей.
2. Естественность — сортируется ли уже упорядоченный массив быстрее, чем случайный, а случайный быстрее, чем упорядоченный в обратном порядке.
3. Производительность в лучшем, среднем, худшем случаях.
4. Требования к дополнительной памяти (и ее порядок).
5. Области применения (например, для сортировок малых почти упорядоченных массивов и др.).

И еще… Могу, конечно, путать, но, как мне кажется, сортировка слиянием существует в двух вариантах — с дополнительной памятью размера O(n) и без дополнительной памяти — т.е. размера O(1).
И производительность этих сортировок весьма различается.

Интересно и хорошо сконцентрировано…
Мне к примеру, надо быстро сортировать 20и битовые данные и их 100 000 000.
Я раньше считал, что самый подходящий способ делёж файла на 30 частей и — Merge Sort.
Сейчас вижу есть другие варианты…
Ну а всё же — что наиболее подходит?

Для пузырька и шейкера легко пишется модификация с запоминанием места последнего обмена. Очевидно, что дальше предыдущей позиции от запомненной ходить при просмотре нет смысла — фрагмент уже отсортирован.

Спасибо, что включили в сравнение std::sort, хотя найти его сразу непросто.

Это всё конечно хорошо, но Представим, что у нас есть повторяющиеся задачи по сортировке, на вход приходят примерно похожие по размеру наборы элементов. Но наборы теоретически могут варьироваться по распределению, поэтому оптимальным может оказаться то один алгоритм, то другой, то их комбинации (начал одним, продолжил другим например). Есть ли решения подобных задач по адаптивной подстройке алгоритмов?
СУБД умеют собирать статистику, но у них, насколько я в курсе, ограниченный набор алгоритмов, и это не сортировка, а хранение: хеш/дерево/битмап…