Изменения

==Описание=='''Сортировка слиянием''' — (англ. ''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> времени.==Принцип работы==*[http[Файл://www.sorting-algorithmsMerging_two_arrays.com/merge-sort Анимированная работа алгоритма (англpng|270px|right|thumb|Пример работы процедуры слияния.)]]

==Принцип [[Файл:Merge sort1.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>

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

MergeSort<tex>T(n)=2T(n/2)+O(A, left, rightn)=4T(n/4): if left + 1 >2O(n)= right: return mid \dots= T(left 1)+ right\log(n) / 2 MergeSortO(A, left, midn) MergeSort=O(n\log(A, mid, rightn) Merge(A, left, mid, right)</tex>.

Пример работы алгоритма показан ==Сравнение с другими алгоритмами==Достоинства:* устойчивая,* можно написать эффективную [[Многопоточная сортировка слиянием|многопоточную сортировку слиянием]],* сортировка данных, расположенных на рисункепериферийных устройствах и не вмещающихся в оперативную память<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/Примеры_реализации_сортировки_слиянием Викиучебник {{---}} Примеры реализации на различных языках программирования]