Изменения

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

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

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

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

Допустим, у У нас есть два отсортированных массива А и B размерами <tex>N_a a</tex> и <tex>N_b b</tex> со­ответственно(фактически это будут две части одного массива, и мы хотим объединить их элементы в один большой отсортирован­ный но для удобства будем писать, что у нас просто два массива). Нам надо получить массив C <tex>c</tex> размером <tex>N_a |a| + N_b |b|</tex> . Для этого можно применить процедуру слия­ния, суть которой слияния. Эта процедура заключается в повторяющемся «отделении» элементатом, наи­меньшего что мы сравниваем элементы массивов (начиная с начала) и меньший из двух имеющихся них записываем в финальный. И затем, в началах исходных массивовмассиве у которого оказался меньший элемент, переходим к следующему элементу и присоединении это­го элемента к концу результирующего массивасравниваем теперь его. Элементы мы переносим до тех порВ конце, пока если один из исходных массивов не закончитсязакончился, мы просто дописываем в финальный другой массив. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего мас­сива. Пример работы процедуры показан на рисунке:[[Файл:Mergearrмы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.png|right|300px|thumb|Пример работы процедуры слияния.]]<br>Алгоритм слияния формально можно записать следующим образом:

Множество отсортированных списков с операцией <pretex>// слияние двух массивов с помощью временного\mathrm{merge (array a, array b) }<// a - левая половина (от l до m), b - правая половина (от m + 1 до r) i = l, j = m + 1, k = 0; array temp; while i <= m and j <= r temptex> является [k++] = (a[jМоноид|моноидом] < b[i]) ? a[j++] : b[i++]; while i <= m temp[k++] = b[i++]; while j <= r temp[k++] = a[j++]; for (int t = 0; t != k; t++) a[t] = temp[t]// в конце a[1, где нейтральным элементом будет пустой список..k] это будет отсортированный массив</pre>

Ниже приведён псевдокод процедуры слияния, который сливает две части массива <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 it2 =Рекурсивный алгоритм0 result : '''int[right - left]''' '''while''' left + it1 < mid '''and''' mid + it2 < right '''if''' a[left + it1] < a[mid + it2] result[it1 + it2] =a[left + it1] it1 +=1 '''else''' result[it1 + it2] = a[mid + it2] it2 += 1 '''while''' left + it1 < mid result[Файл:Merge sort1.png|300px|it1 + it2] = a[left + it1] it1 += 1 '''while''' mid + it2 < right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием result[it1 + it2]= a[mid + it2]Проще всего формализовать этот алгоритм рекурсивным способом. Функция сортирует участок массива от элемента с номером l до элемен­та с номером r: it2 += 1 '''for''' i = 0 '''to''' it1 + it2 a[left + i] = result[i]</code>

===Рекурсивный алгоритм===Функция сортирует подотрезок массива с индексами в полуинтервале <pretex>[left; right)<// r и l tex>.<code style="display: inline- правая и левая граница массива, m - серединаblock"> m = r / 2 // делим на 2 половины'''function''' mergeSortRecursive(a : '''int[n]'''; left, right : '''int'''): '''if m ''' left + 1 >=right '''return''' mid = r (left + right) // условие выхода - если массив стал состоять из 1 элемента2 return sort mergeSortRecursive(a[l..m] // рекурсивная сортировка правой и левой частей, в функцию передаются левая и правая границы массиваleft, mid) sort mergeSortRecursive(a[m+1..r], mid, right) merge (a[l..m], a[m+1..r]left, mid, right) // делаем процедуру слияния 2х отсортированных половинок</precode>

Пример работы алгоритма показан ===Итеративный алгоритм===При итеративном алгоритме используется на рисунке<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>. Распишем это соотношение: <tex>T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n)=\dots=T(1)+\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>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>2См. также==* [[Сортировка кучей]]* [[Быстрая сортировка]]* [[Timsort]]*[[Cортировка слиянием с использованием O(n)</tex> <tex>=</tex> <tex>...</tex> <tex>=</tex> <tex>2^kT(1)</tex> <tex>+</tex> <tex>kO(n).</tex>дополнительной памяти]]

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