Быстрая

Метод основан на подходе "разделяй-и-властвуй". Общая схема такова:

из массива выбирается некоторый опорный элемент a[i],
запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо,
теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого,
для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.

В конце получится полностью отсортированная последовательность.

O(n log n)

Слиянием

Процедура слияния требует два отсортированных массива. Заметив, что массив из одного элемента по определению является отсортированным, мы можем осуществить сортировку следующим образом:

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

В ремя работы сортировки слиянием составляет

Для решения задачи сортировки эти три этапа выглядят так:

Сортируемый массив разбивается на две части примерно одинакового размера;
Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
Два упорядоченных массива половинного размера соединяются в один.

1.1. - 2.1. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).

Cоединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два подмассива. Пусть также, элементы подмассивов в каждом из этих подмассивов отсортированы по возрастанию. Тогда: 3.2. Слияние двух подмассивов в третий результирующий массив. На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счетчики номеров элементов результирующего массива и подмассива из которого был взят элемент увеличиваем на 1. 3.3. "Прицепление" остатка. Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго подмассива в результирующий массив.

Пирамидальная

Пирамида — двоичное дерево, в котором значение каждого элемента больше либо равно значений дочерних элементов.

Заполнив дерево элементами в произвольном порядке, можно легко его отсортировать (легче, чем исходный список элементов), превратив в пирамиду.
Самый большой элемент пирамиды находится в её вершине.
Отделяем вершинный элемент, и записываем его в конец результирующего массива.
На место вершинного элемента записываем элемент из самого нижнего уровня дерева.
Восстанавливаем (пересортировываем) пирамиду.
Самый большой элемент из оставшихся снова в вершине. Снова отделяем его и записываем его в качестве предпоследнего элемента результата, и так далее...
Весь фокус алгоритма в том, что пирамида без дополнительных затрат хранится прямо в исходном массиве. По мере того, как размер пирамиды уменьшается, она занимает всё меньшую часть массива, а результат сортировки записывается начиная с конца массива на освободившиеся от пирамиды места.

Допустим, у нас имеется последовательность чисел:

1, 4, 2, 7, 8, 0, 5, 2, 6.

Чтобы построить пирамиду, нужно добиться, чтобы все элементы номер i были больше элементов номер и . Например, нулевой элемент должен быть больше первого и второго. В нашем примере это не так, поэтому поменяем нулевой элемент и первый:

4, 1, 2, 7, 8, 0, 5, 2, 6.

Первый элемент (единица) должен быть больше третьего (семёрки) и четвёртого (восьмёрки). Для этого поменяем местами единицу и восьмёрку:

4, 8, 2, 7, 1, 0, 5, 2, 6.

Поменяем местами нулевой и первый элементы, чтобы восстановить порядок в начале:

8, 4, 2, 7, 1, 0, 5, 2, 6.

Снова первый и третий не в порядке. Поменяем местами четвёрку и семёрку:

8, 7, 2, 4, 1, 0, 5, 2, 6.

Второй элемент (двойка) должен быть больше пятого (нуля) и шестого (пятёрки). Это не так. Поменяем местами двойку и пятёрку:

8, 7, 5, 4, 1, 0, 2, 2, 6.

Аналогично, четвёрка должна быть больше последних двойки и шестёрки. Поменяем местами четвёрку и шестёрку:

8, 7, 5, 6, 1, 0, 2, 2, 4.

Последние пять элементов не с чем сравнивать; их мы не трогаем. Теперь свойство пирамиды выполнено для всех элементов. Пирамида построена.

Обрати внимание, что первый элемент (семёрка) никак не связан со вторым (пятёркой), поэтому они остаются в «неправильном» порядке.

После того, как пирамида построена, из неё можно получить полностью отсортированный массив. Особенность пирамиды в том, что в её вершине (нулевой элемент) находится максимальный элемент среди всех элементов пирамиды. Но максимальный элемент должен быть в конце массива. Поменяем местами нулевой и последний элементы, и больше не будем последний элемент считать частью пирамиды:

4, 7, 5, 6, 1, 0, 2, 2 | 8.

Пирамида при этом нарушается. Восстанавливаем её так, как строили вначале (восьмёрку при этом не учитываем):

7, 6, 5, 4, 1, 0, 2, 2 | 8.

Снова самый большой элемент пирамиды находится вначале. Этот элемент — самый большой из оставшихся слева от восьмёрки. Поэтому он должен быть перед ней. Меняем местами нулевой элемент и последний элемент пирамиды, и отделяем последний элемент от пирамиды:

2, 6, 5, 4, 1, 0, 2 | 7, 8.

Восстанавливаем пирамиду:

6, 4, 5, 2, 1, 0, 2 | 7, 8.