Изменения

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

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

106 байт добавлено, 15:47, 5 июня 2015
Нет описания правки
Ниже приведён псевдокод процедуры слияния, который сливает две части массива <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>
===Рекурсивный алгоритм===
merge(a, left, mid, right)
</code>
 
===Итеративный алгоритм===
[[Файл:Merge sort itearative.png|300px|right|thumb|Пример работы итеративного алгоритма сортировки слиянием]]
==Сравнение с другими алгоритмами==
===Достоинства===:* Устойчиваяустойчивая,* Сортировка связанных списковсортировка слиянием хорошо параллелится,* Сортировка сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память<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>.
==См. также==
* [[Быстрая сортировка]]
* [[Timsort]]
*[[Cортировка слиянием с использованием O(1) дополнительной памяти]] ==Примечания==<references/>
==Источники информации==
*[http://ru.wikipedia.org/wiki/Mergesort Википедия {{---}} сортировка слиянием]
*[http://en.wikipedia.org/wiki/External_sorting Wikipedia {{---}} External sorting]
*[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 Викиучебник {{---}} Примеры реализации на различных языках программирования]
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/47565»

Навигация