105
правок
Изменения
м
[[Файл:Merge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
[[Файл:Merge sort itearative.png|300px|right|thumb|Пример работы итеративного алгоритма сортировки слиянием]]
===Достоинства===:* устойчивая.,===Недостатки===* можно написать эффективную [[Многопоточная сортировка слиянием|многопоточную сортировку слиянием]],* при любых входных сортировка данных время работы , расположенных на периферийных устройствах и не вмещающихся в оперативную память<ref>[http://en.wikipedia.org/wiki/External_sorting Wikipedia {{---}} <tex>O(n\log{n})External sorting]</texref>,.Недостатки:
Нет описания правки
'''Сортировка слиянием''' (англ. ''Merge sort'') {{---}} алгоритм сортировки, предложенный Джоном фон Нейманом в 1945 году. Это устойчивый алгоритм, использующий <tex>O(n)</tex> дополнительной памяти и работающий за <tex>O(n</tex> <tex>\log (n))</tex> времени.
==Принцип работы==
[[Файл:Merging_two_arrays.png|270px|right|thumb|Пример работы процедуры слияния.]]
[[Файл:Merge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
[[Файл:Merge sort itearative.png|300px|right|thumb|Пример работы итеративного алгоритма сортировки слиянием]]
Алгоритм использует принцип «разделяй и властвуй»: задача разбивается на подзадачи меньшего размера, которые решаются по отдельности, после чего их решения комбинируются для получения решения исходной задачи. Конкретно процедуру сортировки слиянием можно описать следующим образом:
Ниже приведён псевдокод процедуры слияния, который сливает две части массива <tex>a</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>.
<code style="display: inline-block">
merge(a, left, mid, right)
</code>
===Итеративный алгоритм===
При итеративном алгоритме используется на <tex>O(\log n)</tex> меньше памяти, которая раньше тратилась на рекурсивные вызовы.
<code style="display: inline-block">
==Время работы==
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> {{---}} время сортировки массива длины <tex>n</tex>, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>
<tex>O(n)</tex> {{---}} время, необходимое на то, чтобы слить два массивадлины <tex>n</tex>. Распишем это соотношение:
<tex>T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n)=\dots=2^kTT(1)+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>.
==Сравнение с другими алгоритмами==
* требуется дополнительно <tex>O(n)</tex> памяти, но можно модифицировать до <tex>O(1)</tex>.
* [[Быстрая сортировка]]
* [[Timsort]]
*[[Cортировка слиянием с использованием O(1) дополнительной памяти]] ==Примечания==<references/>
==Источники информации==
*[http://ru.wikipedia.org/wiki/Mergesort Википедия {{---}} сортировка слиянием]
*[http://www.sorting-algorithms.com/merge-sort Визуализатор]
*[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 Примеры_реализации_сортировки_слиянием Викиучебник {{---}} Примеры реализации на различных языках программирования]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: СортировкаСортировки]]
[[Категория: Сортировки на сравнениях]]
