Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов). Является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена. Принципиальное отличие состоит в том, что после каждого прохода элементы делятся на две независимые группы.
| Лучшая | Средняя | Худшая |
|---|---|---|
| n log n | n log n | n² |
Если в каждой итерации каждый из подмассивов будет делиться на два равных по величине массива
4 1 3 2 6 5Если на каждом этапе массив будет разделяться на вырожденный подмассив из одного опорного элемента и на подмассив из всех остальных элементов
0 1 2 3 4 5 6 7 8 9 2 5 1 6 3 7 0 8 4 9На упорядоченных (частично или обратно) массивах, нерекурсивная форма примерно в 2-4 раза медленнее, чем рекурсивная. Но, иногда, когда массив из большого количества случайных величин вынуждает рекурсивную форму совершать множество рекурсивных вызовов и сложных сравнений (например, строк или больших чисел), нерекурсивная форма вполне может выигрывать.