63
правки
Изменения
Нет описания правки
'''Сортировка слиянием''' — алгоритм сортировки. Он был предложен Джоном фон Нейманом в 1945 году.
Это устойчивый алгоритм, использующий <tex>O(n)</tex> дополнительной памяти и <tex>O(n</tex> <tex>\log(n))</tex> времени.*[http://www.sorting-algorithms.com/merge-sort Анимированная работа алгоритма (англ.)]
==Принцип работы==
У нас есть два массива <tex>A</tex> и <tex>B</tex> (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив <tex>C</tex> размером <tex>|A| + |B|</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
Ниже приведён псевдокод процедуры слияния, который сливает две части массива A — <tex>[left; mid) </tex> и <tex>[mid; right)</tex>
Merge(A, : '''int[1..N]'''; left, mid, right: '''int'''): it1 = 0 it2 = 0 result = new : '''int[right - left]'''
===Рекурсивный алгоритм===
Функция сортирует подотрезок массива с индексами в полуинтервале [left; right).
MergeSort(A, : '''int[1..N]'''; left, right: '''int'''): '''if ''' left + 1 >= right: return mid = (left + right) / 2 MergeSort(A, left, mid) MergeSort(A, mid, right) Merge(A, left, mid, right)
Пример работы алгоритма показан на рисунке:
(<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>2O(n)</tex> <tex>=</tex> <tex>...</tex> <tex>\dots=</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</tex> <tex>O(n)</tex>. Так как <tex>T(1)</tex> — константа, то <tex>T(n)=O(n)+\log n </tex> <tex>O(n)=O(n\log n)</tex>.
==Источники информации==
*[http://ru.wikipedia.org/wiki/Mergesort Википедия {{---}} сортировка слиянием]
==Ссылки==
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировка]][[Категория: Сортировкина сравнениях]]
