Все началось с того, что я почему-то написал свою реализацию классического алгоритма быстрой сортировки QuickSort. И все бы хорошо, но я, конечно, решил померяться достоинством с STL’ой реализацией. Результат был очевиден, и я даже не хочу приводить цифры.

В общем, я открыл файл algorithm из STL’я в Visual Studio 2008 и часок покопался в нем. Вот результаты моих “исследований”.

Начнем с нестабильной сортировки std::sort().

• основа: алгоритм быстрой сортировки QuickSort (почти как у меня)
• выбор опорного элемента — центральный по индексу элемент в сортируемом фрагменте
• после каждого выбора опорного элемента:
  • начальный, опорный и последний элементы сортируются между собой (их всего три, так что тут это делается тремя последовательными if‘ами)
  • если длина сортируемого фрагмента менее более 40, то отрезок делится 8 частeй (длина каждой части S = 1/8*N) и для троиц элементов (1, S, 2*S), (N/2 - S, N/2, N/2 + S) и (N - 2*S, N - S, N) делается такая же минисортировка, как и на предыдущем шаге (где число элементов было меньше 40)
  • далее происходит обычная для QuickSort процедура деления фрагмента на две части с использованием опорного элемента (цикл по перебрасыванию элементов, меньших опорного направо, а больших — налево)
• затем вся процедура рекурсивно повторяется для левой и правой частей

Количество рекурсивных операций не идет до победного конца, как в чистом QuickSort. Если количество итераций (процедур разделения массива) превысило 1.5*log2(N), где N длина всего массива, то рекурсивные операции прекращаются. Если количество оставшихся недосортированных элементов меньше 32-х, то фрагмент досортируется методом вставки InsertionSort (этот метод имеет общую сложность O(N2) и для больших массивов не используется, но на малых длинах он быстрее всех из-за простоты). Если же остается более 32-х элементов, то досортировка происходит пирамидальным методом HeapSort в чистом его виде.

Видимо все эти ухищрения для уменьшения накладных расходов QuickSort на малых массивах.

Вот такая вот далеко непрямолинейная реализация.

Далее.

Стабильная сортировка std::stable_sort() реализована алгоримом слияния MergeSort. Особых ухищрений по сравнению с чистным алгоритмом я не нашел. Разве что малые фрагменты (короче 32-х элементов) досортировываются методом вставки InsertionSort, как и в случае с QuickSort.

Частичая сортировка std::partial_sort() реализована в чистом виде пирамидальным методом HeapSort.

Вывод: Читать исходники очень интересно. Особенно хорошие исходники.