139
правок
Изменения
Нет описания правки
==Описание==
'''Сортировка слиянием''' — алгоритм сортировки. Он был предложен Джоном фон Нейманом в 1945 году.
Это устойчивый алгоритм, использующий <tex>O(n)</tex> дополнительной памяти и <tex>O(n</tex> <tex>\log(n))</tex> времени.
*[http://www.sorting-algorithms.com/merge-sort Анимированная работа алгоритма (англ.)]
==Принцип работы==
[[Файл:Merge-sort-example.jpg|right|300px|thumb|Пример работы процедуры слияния.]]
Этот алгоритм использует принцип «разделяй и властвуй». Этот принцип заключается в том, что исходная задача разбивается на подзадачи меньшего размера, а потом они решаются рекурсивным методом или же конкретно, если их размер мал. Потом из решения объединяются и получается решение основной (исходной) задачи.
===Слияние двух массивов===
У нас есть два массива <tex>A</tex> и <tex>B</tex>. Нам надо получить массив <tex>C</tex> размером <tex>sizeof(A) + sizeof(B)</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
// left - левая граница, right - правая, middle - середина
merge(array a, int left, int middle, int right)
i = left, j = middle, k = 0;
array temp = new array[sizeof(a) + sizeof(b)];
while i <= middle and j < right
temp[k++] = (a[j] < ba[i]) ? a[j++] : ba[i++];
while i <= middle
temp[k++] = ba[i++];
while j < right
temp[k++] = a[j++];
// в конце a[1..k] это будет отсортированный массив
</pre>
==Рекурсивный алгоритм==
[[Файл:Merge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
Функция сортирует участок массива от элемента с номером left до элемента с номером right:. Будем реализовывать так, что бы производилась сортировка полуинтервала [left, right)
right и left — правая и левая граница массива, middle — середина.
Пример работы алгоритма показан на рисунке:
==Время работы==
(<tex>O(n)</tex> — это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:
<tex>T(n)</tex> <tex>=</tex> <tex>2T(n/2)</tex> <tex>+</tex> <tex>O(n)</tex> <tex>=</tex> <tex>4T(n/4)</tex> <tex>+</tex> <tex>2*O2O(n)</tex> <tex>=</tex> <tex>...</tex> <tex>=</tex> <tex>2^kT(1)</tex> <tex>+</tex> <tex>kO(n).</tex>
Осталось оценить <tex>k</tex>. Мы знаем, что <tex>2^k=n</tex>, а значит <tex>k=\log(n)</tex>. Уравнение примет вид <tex>T(n)=nT(1)+ \log(n)O(n)</tex>. Так как <tex>T(1)</tex> — константа, то <tex>T(n)=O(n)+\log(n)O(n)=O(n\log(n))</tex>.
