63
правки
Изменения
Нет описания правки
===Слияние двух массивов===
У нас есть два массива <tex>Aa</tex> и <tex>Bb</tex> (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив <tex>Cc</tex> размером <tex>|Aa| + |Bb|</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
Два отсортированных списка с операцией <tex>merge</tex> являются моноидом.
Ниже приведён псевдокод процедуры слияния, который сливает две части массива <tex>Aa</tex> {{---}} <tex>[left; mid)</tex> и <tex>[mid; right)</tex><code style="display: inline-block">
'''function''' merge(a : '''int[n]'''; left, mid, right : '''int'''):
it1 = 0
'''for''' i = 0 '''to''' it1 + it2
a[left + i] = result[i]
</code>
===Рекурсивный алгоритм===
Функция сортирует подотрезок массива с индексами в полуинтервале <tex>[left; right)</tex>.
[[Файл:Merge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
<code style="display: inline-block">
'''function''' mergeSortRecursive(a : '''int[n]'''; left, right : '''int'''):
'''if''' left + 1 >= right
mergeSortRecursive(a, mid, right)
merge(a, left, mid, right)
===Итеративный алгоритм===
'''for''' i = 1 '''to''' n, i *= 2
'''for''' j = left 0 '''to''' right n - i, j += 2 * i merge(a, j, j + i, min(j + 2 * i, rightn)) </code>
==Время работы==
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> {{---}} время сортировки массива длины <tex>n</tex>, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>
Осталось оценить <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>.
==См. также==
* [[Быстрая сортировка]]
*[[Cортировка слиянием с использованием O(1) дополнительной памяти]]
===Ссылки===
*[http://ru.wikipedia.org/wiki/Mergesort Википедия {{---}} сортировка слиянием]
*[http://www.sorting-algorithms.com/merge-sort Визуализатор]
*[http://ru.wikibooks.org/wiki/%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC Викиучебник {{---}} Примеры реализации на различных языках программирования]
