Изменения

'''Сортировка слиянием''' (англ. ''Merge sort'') {{---}} алгоритм сортировки, пред­ло­женный Джо­ном фон Ней­ма­ном в 1945 го­ду. Это устойчивый алгоритм, использующий <tex>O(n)</tex> дополнительной памяти и работающий за <tex>O(n</tex> <tex>\log (n))</tex> времени.

У нас есть два массива <tex>Aa</tex> и <tex>Bb</tex> (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив <tex>Cc</tex> размером <tex>|Aa| + |Bb|</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.

Ниже приведён псевдокод процедуры слияния, который сливает две части массива Множество отсортированных списков с операцией <tex>A</tex> {\mathrm{---}merge} </tex>является [left; mid)</tex> и <tex>[mid; right)</tex>Моноид|моноидом]], где нейтральным элементом будет пустой список.

Ниже приведён псевдокод процедуры слияния, который сливает две части массива <tex>a</tex> {{---}} <tex>[left; mid)</tex> и <tex>[mid; right)</tex><code style="display: inline-block"> '''function''' merge(a : '''int[Nn]'''; left, mid, right : '''int'''):

[[Файл<code style="display:Merge sort1.png|300px|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]inline-block"> '''function''' mergeSortRecursive(a : '''int[Nn]'''; left, right : '''int'''):

Функция сортирует подотрезок массива с индексами в полуинтервале При итеративном алгоритме используется на <tex>[left; rightO(\log n)</tex>меньше памяти, которая раньше тратилась на рекурсивные вызовы.<code style="display: inline-block"> '''function''' mergeSortIterative(a : '''int[n]'''): '''for''' i = 1 '''to''' n, i *= 2 '''for''' j = 0 '''to''' n - i, j += 2 * i merge(a, j, j + i, min(j + 2 * i, n))</code>

<tex>O(n)</tex> {{---}} время, необходимое на то, чтобы слить два массива. Распишем это соотношение: длины <tex>T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n)=\dots=2^kT(1)+kO(n)</tex>.Распишем это соотношение:

Осталось оценить <tex>k</tex>. Мы знаем, что <tex>2^k=n</tex>, а значит <tex>k=\log n</tex>. Уравнение примет вид <tex>T(n)=nT2T(1n/2)+ \log n</tex> <tex>O(n)<=4T(n/tex>. Так как <tex>T(14)</tex> {{---}} константа, то <tex>T+2O(n)=O\dots=T(n1)+\log (n </tex> <tex>)O(n)=O(n\log (n))</tex>.

==Источники информацииСравнение с другими алгоритмами==Достоинства:* устойчивая,*можно написать эффективную [[Многопоточная сортировка слиянием|многопоточную сортировку слиянием]],* сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память<ref>[http://ruen.wikipedia.org/wiki/Mergesort Википедия External_sorting Wikipedia {{---}} сортировка слияниемExternal sorting]</ref>.Недостатки:* требуется дополнительно <tex>O(n)</tex> памяти, но можно модифицировать до <tex>O(1)</tex>.

* [[Timsort]]*[[Cортировка слиянием с использованием O(1) дополнительной памяти]] ==Примечания==<references/> ==Источники информации==*[http://ru.wikipedia.org/wiki/Mergesort Википедия {{---}} сортировка слиянием]

*[httphttps://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 Примеры_реализации_сортировки_слиянием Викиучебник {{---}} Примеры реализации на различных языках программирования] 

[[Категория: СортировкаСортировки]]