Быстрая сортировка
Сортировка слиянием
Сортировка слиянием — один из распространенных алгоритмов рекурсивной сортировки. В ее основе лежит замечание, согласно которому слияние двух отсортированных списков выполняется быстро. Список из одного элемента уже отсортирован, поэтому при сортировке слиянием список разбивается на одноэлементные куски, которые затем постепенно сливаются. Поэтому вся деятельность заключается в слиянии двух списков.
Быстрая сортировка — один из наиболее популярных алгоритмов рекурсивной сортировки. При быстрой сортировке после выбора в списке элемента список с его помощью делится на две части. В первую часть попадают все элементы, меньшие выбранного, во вторую — большие выбранного. В среднем такая сортировка эффективна, однако в наихудшем случае ее эффективность такая же, как у сортировки вставками и у пузырьковой сортировки.
При быстрой сортировке в списке выбирается элемент, называемый осевым, а затем список переупорядочивается таким образом, что все элементы, меньшие осевого, оказываются перед ним, а большие элементы — за ним. В каждой из частей списка элементы не упорядочиваются. Если п — окончательное положение осевого элемента, то нам известно лишь, что все значения в позициях с первой по п - 1 меньше осевого, а значения с номерами от п + 1 до N— больше осевого. Далее алгоритм вызывается рекурсивно на каждой из двух частей.