Изменения

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

Это ста­биль­ный ал­го­ритм сор­ти­ров­ки, использующий <tex>O(n)</tex> дополнительной памяти и <tex>O(n</tex> <tex>lg(n))</tex> времени==Принцип работы==[[Файл:Merging_two_arrays.png|270px|right|thumb|Пример работы процедуры слияния.]]

=Принцип [[Файл:Merge sort1.png|300px|right|thumb|Пример работы=Данный алгоритм — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи. Про­це­ду­ра слия­ния тре­бу­ет два от­сор­ти­ро­ван­ных мас­си­ва. За­ме­тив, что мас­сив из од­но­го эле­мен­та по опре­де­ле­нию яв­ля­ет­ся от­сор­ти­ро­ван­ным, мы мо­жем осу­ще­ствить сор­ти­ров­ку сле­дую­щим об­ра­зом: 1. Раз­бить имею­щие­ся эле­мен­ты мас­си­ва на па­ры и осу­ще­ствить слия­ние эле­мен­тов каж­дой па­ры, по­лу­чив от­сор­ти­ро­ван­ные це­поч­ки дли­ны 2 (кро­ме, быть мо­жет, од­но­го эле­мен­та, для ко­то­ро­го не на­шлось па­ры).алгоритма сортировки слиянием]]

2. Раз­бить имею­щие­ся от­сор­ти­ро­ван­ные це­поч­ки на па­ры, и осу­ще­ствить слия­ние це­по­чек каж­дой па­ры[[Файл:Merge sort itearative.png|300px|right|thumb|Пример работы итеративного алгоритма сортировки слиянием]]

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

=Слияние 2-х массивов=Допустим, у нас есть два отсортированных массива А и B размерами <tex>N_a </tex> и <tex>N_b </tex> со­ответственно, и мы хотим объединить их элементы # Если в рассматриваемом массиве один большой отсортирован­ный массив C размером <tex>N_a + N_b </tex> . Для этого можно применить процедуру слия­нияэлемент, суть которой заключается в повторяющемся «отделении» элемента, наи­меньшего из двух имеющихся в началах исходных массивов, и присоединении это­го элемента к концу результирующего массивато он уже отсортирован {{---}} алгоритм завершает работу. Элементы мы переносим до тех пор# Иначе массив разбивается на две части, пока один из исходных массивов не закончитсякоторые сортируются рекурсивно. # После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего мас­сива. Пример работы процедуры показан на рисунке:[[Файл:Mergearr.png|right|300px|thumb|Пример работы процедуры сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.]]<br>Алгоритм слияния формально можно записать следующим образом:

<pre>// слияние ===Слияние двух массивов с помощью временного===merge (array У нас есть два массива <tex>a, array </tex> и <tex>b) <// a - левая половина tex> (от l до m)фактически это будут две части одного массива, но для удобства будем писать, b - правая половина (от m + 1 до rчто у нас просто два массива) i = l, j = m + 1, k = 0; array temp; while i . Нам надо получить массив <= m and j tex>c<= r temp[k++] = (a[j] /tex> размером < b[i]) ? tex>|a[j++] : b[i++]; while i <= m temp[k+| +] = |b[i++]; while j |<= r temp[k++] = a[j++]; for /tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (int t = 0; t != k; t++начиная с начала) a[t] = temp[t]// и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце a[1, если один из массивов закончился, мы просто дописываем в финальный другой массив.После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.k] это будет отсортированный массив</pre>

=Рекурсивный алгоритм=Множество отсортированных списков с операцией <tex>\mathrm{merge}</tex> является [[Файл:Merge sort1.png|300pxМоноид|right|thumb|Пример работы рекурсивного алгоритма сортировки слияниеммоноидом]]Проще всего формализовать этот алгоритм рекурсивным способом, где нейтральным элементом будет пустой список. Функ­ция сортирует участок массива от элемента с номером a до элемен­та с номером b:

Ниже приведён псевдокод процедуры слияния, который сливает две части массива <pretex>a</tex> {{---}} <tex>[left; mid)</ r tex> и l <tex>[mid; right)</tex><code style="display: inline- правая и левая граница массиваblock"> '''function''' merge(a : '''int[n]'''; left, mid, m right : '''int'''): it1 = 0 it2 = 0 result : '''int[right - серединаleft]''' m = r / 2 // делим на 2 половины '''while''' left + it1 < mid '''and''' mid + it2 < right '''if m ''' a[left + it1] < a[mid + it2] result[it1 + it2] =a[left + it1] it1 += r // условие выхода - если массив стал состоять из 1 элемента return '''else''' sort result[it1 + it2] = a[l..mmid + it2] // рекурсивная сортировка правой и левой частей, в функцию передаются левая и правая границы массива sort it2 += 1 '''while''' left + it1 < mid result[it1 + it2] = a[mleft +it1] it1 += 1..r '''while''' mid + it2 < right result[it1 + it2] merge (= a[l..mmid + it2], it2 += 1 '''for''' i = 0 '''to''' it1 + it2 a[mleft +1..ri] = result[i]) // делаем процедуру слияния 2х отсортированных половинок</precode>

Пример работы алгоритма показан на рисунке===Рекурсивный алгоритм===Функция сортирует подотрезок массива с индексами в полуинтервале <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>TO(\log n)</tex> - время сортировки массива длины nменьше памяти, тогда для сортировки слиянием справедливо которая раньше тратилась на рекурсивные вызовы.<texcode style="display: inline-block">T '''function''' mergeSortIterative(a : '''int[n]'''): '''for''' i =2T(1 '''to''' n/, i *= 2) '''for''' j = 0 '''to''' n - i, j +O(n)</tex> <br>= 2 * i merge(<tex>Oa, j, j + i, min(j + 2 * i, n))</texcode> - это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:

==Время работы==Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> {{---}} время сортировки массива длины <tex>=</tex> <tex>2T(n/2)</tex> , тогда для сортировки слиянием справедливо <tex>+</tex> <tex>OT(n)</tex> <tex>=</tex> <tex>4T2T(n/42)</tex> <tex>+</tex> <tex>2*O(n)</tex> <texbr>=</tex> <tex>...</tex> <tex>=</tex> <tex>2^kTO(1n)</tex> {{---}} время, необходимое на то, чтобы слить два массива длины <tex>+n</tex> <tex>kO(n).</tex>Распишем это соотношение:

Осталось оценить <tex>k</tex>. Мы знаем, что <tex>2^k=n</tex>, а значит <tex>k=\log(n)</tex>. Уравнение примет вид <tex>T(n)=nT2T(1n/2)+ \logO(n)O=4T(n)</tex>. Так как <tex>T(14)</tex> - константа, то <tex>T+2O(n)=O\dots=T(n1)+\log(n)O(n)=O(n\log(n))</tex>.

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

<tex>==См. также==* [[Сортировка кучей]]* [[Быстрая сортировка]]* [[Timsort]]* [[Cортировка слиянием с использованием O(n1)</tex> дополнительной памяти для массива.]]

==Примечания==<tex>O(lg(n))<references/tex> дополнительной памяти для связных списков.

<tex>O(n<==Источники информации==*[http:/tex> <tex>lg(n))</tex> времениru.wikipedia.org/wiki/Mergesort Википедия {{---}} сортировка слиянием]*[http://www.sorting-algorithms.com/merge-sort Визуализатор]*[https://ru.wikibooks.org/wiki/Примеры_реализации_сортировки_слиянием Викиучебник {{---}} Примеры реализации на различных языках программирования]