Сортировка слиянием
Описание
Сортировка слиянием — алгоритм сортировки. Он был предложен Джоном фон Нейманом в 1945 году.
Это устойчивый алгоритм, использующий дополнительной памяти и времени.
Принцип работы
Этот алгоритм использует принцип «разделяй и властвуй». Этот принцип заключается в том, что исходная задача разбивается на подзадачи меньшего размера, а потом они решаются рекурсивным методом или же конкретно, если их размер мал. Потом из решения объединяются и получается решение основной (исходной) задачи.
Для процедуры слияния требуется два отсортированных массива. Зная, что массив из одного элемента по определению отсортирован, мы можем разработать такой алгоритм:
- Массив разбивается на равные (или почти равные) части, до тех пор, пока он не разобьется на части, размер которых равен единице.
- Далее каждая из частей сортируется по отдельности. Или нет, в случае, если это у нас одиночный элемент.
- После происходия слияние двух упорядоченных массивов в один.
Слияние двух массивов
У нас есть два массива и (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив размером . Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
Алгоритм слияния формально можно записать следующим образом:
Будет происходить слияние частей [left, middle) и [middle, right]
// слияние двух частей одного массива с помощью временного
// left - левая граница, right - правая, middle - середина
merge(array a, int left, int middle, int right)
i = left, j = middle, k = 0;
array temp = new array[a.size()];
while i < middle and j <= right
if (a[j] < a[i])
temp[k++] = a[j++];
else
temp[k++] = a[i++];
while i < middle
temp[k++] = a[i++];
while j <= right
temp[k++] = a[j++];
for (int t = 0; t != k; t++)
a[t] = temp[t];
// в конце a[1..k] это будет отсортированный массив
Рекурсивный алгоритм
Функция сортирует участок массива от элемента с номером left до элемента с номером right. Будем реализовывать так, что бы производилась сортировка полуинтервала [left, right)
right и left — правая и левая граница массива, middle — середина.
sort(array a, int left, int right)
middle = left + (right - left ) / 2;
if left >= right
return;
sort(a, left, middle);
sort (a, middle, right);
merge(array a, left, middle, right);
Пример работы алгоритма показан на рисунке:
Время работы
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай — время сортировки массива длины n, тогда для сортировки слиянием справедливо
( — это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:
Осталось оценить . Мы знаем, что , а значит . Уравнение примет вид . Так как — константа, то .
