Изменения

Перейти к: навигация, поиск

Сортировка слиянием

577 байт убрано, 15:42, 17 января 2019
м
Нет описания правки
'''Сортировка слиянием''' (англ. ''Merge sort'') {{---}} алгоритм сортировки, пред­ло­женный Джо­ном фон Ней­ма­ном в 1945 го­ду. Это устойчивый алгоритм, использующий <tex>O(n)</tex> дополнительной памяти и работающий за <tex>O(n</tex> <tex>\log (n))</tex> времени.
==Принцип работы==
==Время работы==
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> {{---}} время сортировки массива длины <tex>n</tex>, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>
<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://en.wikipedia.org/wiki/External_sorting Wikipedia {{---}} External sorting]</ref>.
Недостатки:
* при любых входных данных время работы {{---}} <tex>O(n\log{n})</tex>,
* требуется дополнительно <tex>O(n)</tex> памяти, но можно модифицировать до <tex>O(1)</tex>.
*[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 Примеры_реализации_сортировки_слиянием Викиучебник {{---}} Примеры реализации на различных языках программирования]

Навигация