Основывается на выборе опорного элемента и дальнейшей сортировке элементов на группы: меньше / равны / большего опорного. В качестве опорного элемента эффективно выбирать медианное значение. Медианное значение - значение, которое находится в середине отсортированного списка. Алгоритм:
1. Выбираем опорный элемент. 2. Перераспределяем элементы относительно опорного - слева меньше, справа больше. 3. Рекурсивно выполняем п 1 и п 2 на полученных подмассивах. 4. Рекурсия не применяется, если в подмаслила остался 1 элемент или вообще ни одного.
Делим массив на две части (левую и правую). Левую часть считаем отсортированной. Изначально первый элемент массива оставляем в левой части, все остальное относим к правой (не отсортированной). Начинаем перемещаться по не отсортированной части. Берем первый элемент, и попарно сравнивая с соседними, ищем ему место в отсортированной части. Например, имеем массив [ 4 6 2 1 ]. Выполняем сортировку:
1. Делим на 2 части: [ 4 | 6 2 1 ]. 2. Берем элемент 6 и ставим его на подходящее место в отсортированной части: [ 4 6 | 2 1 ]. 3. Ставим на свое место элемент 2: [ 2 4 6 | 1 ]. 4. Ставим на свое место элемент 1: [ 1 2 4 6 ].
