Изменения

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

Это устойчивый ал­го­ритм, использующий <tex>O(n)</tex> дополнительной памяти и <tex>O(n</tex> <tex>\log(n))</tex> времени==Принцип работы==[[Файл:Merging_two_arrays.png|270px|right|thumb|Пример работы процедуры слияния.]]*[[httpФайл://www.sorting-algorithmsMerge sort1.com/merge-sort Анимированная работа png|300px|right|thumb|Пример работы рекурсивного алгоритма (англ.)сортировки слиянием]]

==Принцип работы==[[Файл:Merge-sort-exampleitearative.png|300px|right|300px|thumb|Пример работы процедуры слияния.итеративного алгоритма сортировки слиянием]]Этот алгоритм использует принцип «разделяй и властвуй». Этот принцип заключается в том, что исходная задача разбивается на подзадачи меньшего размера, а потом они решаются рекурсивным методом или же конкретно, если их размер мал. Потом из решения объединяются и получается решение основной (исходной) задачи.

Для процедуры слияния требуется два отсортированных массива. ЗнаяАлгоритм использует принцип «разделяй и властвуй»: задача разбивается на подзадачи меньшего размера, что массив из одного элемента которые решаются по определению отсортированотдельности, мы можем разработать такой алгоритмпосле чего их решения комбинируются для получения решения исходной задачи. Конкретно процедуру сортировки слиянием можно описать следующим образом:

# Массив разбивается на равные (или почти равные) части, до тех порЕсли в рассматриваемом массиве один элемент, пока то он не разобьется на части, размер которых равен единицеуже отсортирован {{---}} алгоритм завершает работу.# Далее каждая из частей сортируется по отдельности. Или нет, в случаеИначе массив разбивается на две части, если это у нас одиночный элементкоторые сортируются рекурсивно.# После происходия слияние сортировки двух упорядоченных массивов в одинчастей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.

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

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

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

'''while ''' left + it1 < mid '''and ''' mid + it2 < right: '''if A''' a[left + it1] < Aa[mid + it2]: result[it1 + it2] = Aa[left + it1] it1 += 1 '''else:''' result[it1 + it2] = Aa[mid + it2] it2 += 1

'''while ''' left + it1 < mid: result[it1 + it2] = Aa[left + it1] it1 += 1

'''while ''' mid + it2 < right: result[it1 + it2] = Aa[mid + it2] it2 += 1

'''for ''' i = 0 '''to ''' it1 + it2: A a[left + i] = result[i]</code>

Функция сортирует подотрезок массива с индексами в полуинтервале <tex>[left; right)</tex>.<code style="display: inline-block"> '''function''' mergeSortRecursive(a : '''int[Файлn]'''; left, right : '''int'''):Merge sort1.png|300px| '''if''' left + 1 >= right '''return''' mid = (left + right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]) / 2Функция сортирует участок массива от элемента с номером mergeSortRecursive(a, left до элемен­та с номером , mid) mergeSortRecursive(a, mid, right. Будем реализовывать так) merge(a, что бы производилась сортировка полуинтервала [left, mid, right)</code> ===Итеративный алгоритм===При итеративном алгоритме используется на <tex>O(\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>

right и left — правая и левая граница ==Время работы==Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> {{---}} время сортировки массивадлины <tex>n</tex>, middle — серединатогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br><tex>O(n)</tex> {{---}} время, необходимое на то, чтобы слить два массива длины <tex>n</tex>.Распишем это соотношение:

<pretex>sortT(array a, int left, int rightn) middle = left 2T(n/2)+ O(right - left n) =4T(n/ 2; if left >4)+2O(n)=\dots= right return; sortT(a, left, middle1); sort +\log(a, middle, rightn); mergeO(array a, left, middle, rightn)=O(n\log(n));</pretex>.

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

==Время работыСм. также==Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> — время сортировки массива длины n, тогда для сортировки * [[Сортировка кучей]]* [[Быстрая сортировка]]* [[Timsort]]* [[Cортировка слиянием справедливо <tex>T(n)=2T(n/2)+с использованием O(n1)</tex> <br>(<tex>O(n)</tex> — это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:дополнительной памяти]]

<tex>T(n)</tex> <tex>=</tex> <tex>2T(n/2)</tex> <tex>+</tex> <tex>O(n)</tex> <tex>=</tex> <tex>4T(n/4)</tex> <tex>+</tex> <tex>2O(n)</tex> <tex>Примечания=</tex> <tex>...</tex> <tex>=<references/tex> <tex>2^kT(1)</tex> <tex>+</tex> <tex>kO(n).</tex>

Осталось оценить <tex>k<==Источники информации==*[http://tex>ru.wikipedia. Мы знаем, что <tex>2^k=n<org/tex>, а значит <tex>k=\log n<wiki/tex>. Уравнение примет вид <tex>T(n)=nT(1)+ \log n<Mergesort Википедия {{---}} сортировка слиянием]*[http:/tex> <tex>O(n)</tex>www.sorting-algorithms. Так как <tex>T(1)<com/tex> — константа, то <tex>T(n)=O(n)+\log n <merge-sort Визуализатор]*[https:/tex> <tex>O(n)=O(n\log n)</tex>ru.wikibooks.org/wiki/Примеры_реализации_сортировки_слиянием Викиучебник {{---}} Примеры реализации на различных языках программирования]