Изменения

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

Кро­ме то­го, сор­ти­ров­ка слия­ни­ем — чуть ли не един­ствен­ный ал­го­ритм, ко­то­рый мо­жет быть эф­фек­тив­но ис­поль­зо­ван для сор­ти­ров­ки та­ких ст­рук­тур дан­ных, как свя­зан­ные спис­ки==Принцип работы==[[Файл:Merging_two_arrays. По­сле­до­ва­тель­ная ра­бо­та с эле­мен­та­ми мас­си­ва зна­чи­тель­но уве­ли­чи­ва­ет ско­рость сор­ти­ров­ки в си­сте­мах с кэ­ши­ро­ва­ни­емpng|270px|right|thumb|Пример работы процедуры слияния.]]

Сор­ти­ров­ка слия­ни­ем — ста­биль­ный ал­го­ритм сор­ти­ров­ки[[Файл:Merge sort1. Это озна­ча­ет, что по­ря­док «рав­ных» эле­мен­тов не из­ме­ня­ет­ся в ре­зуль­та­те ра­бо­ты ал­го­рит­ма. В не­ко­то­рых за­да­чах это свой­ство до­ста­точ­но важ­но.Этот ал­го­ритм был пред­ло­жен Джо­ном фон Ней­ма­ном в 1945 го­дуpng|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]

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

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

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

===Слияние 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|center|500px|thumb|Пример работы процедуры слияния.]]<br>Алгоритм слияния формально можно записать следующим образом:

a = 0; b = 0; While (a < <tex>n_a</tex>) and (b < <tex>n_b</tex>) If A[a] Множество отсортированных списков с операцией <tex>\leqslantmathrm{merge}</tex> B[b] C[a + b] = Aявляется [a]; a = a + 1; Else C[a + bМоноид|моноидом] = B[b]; b = b + 1; End; End; If a < <tex>n_a</tex> Copy remain part of A Else Copy remain part of B End;, где нейтральным элементом будет пустой список.

===Рекурсивный алгоритм===Проще всего формализовать этот алгоритм рекурсивным способом. Функ­ция Функция сортирует участок подотрезок массива от элемента с номером a до элемен­та с номером bиндексами в полуинтервале <tex>[left; right)</tex>.<code style="display:inline-block"> Function MergeSort'''function''' mergeSortRecursive(a: '''int[n]'''; left,bright : '''int'''): If b '''if''' left + 1 >= a then Exit;right '''return''' c mid = (a left + bright)/2; Mergesort mergeSortRecursive(a,cleft, mid); MergeSort mergeSortRecursive(c + 1a, mid,bright); Merge fragments merge(a,c) and (c + 1left, mid,bright); End</code>

Пример работы алгоритма показан ===Итеративный алгоритм===При итеративном алгоритме используется на <tex>O(\log n)</tex> меньше памяти, которая раньше тратилась на рисункерекурсивные вызовы.<code style="display:inline-block"> '''function''' mergeSortIterative(a : '''int[[Файлn]'''):Merge sort1.png|500px|center|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]] '''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) + 2*O2O(n) = ... \dots= 2^kTT(1) + kO\log(n)O(n)=O(n\log(n))</tex>.

Осталось оценить ==Сравнение с другими алгоритмами==Достоинства:* устойчивая,* можно написать эффективную [[Многопоточная сортировка слиянием|многопоточную сортировку слиянием]],* сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память<texref>k<[http://tex>en.wikipedia. Мы знаем, что <tex>2^k=n<org/wiki/tex>, а значит <tex>k=\log(n)External_sorting Wikipedia {{---}} External sorting]</texref>. Уравнение примет вид Недостатки:* требуется дополнительно <tex>T(n)=nT(1)+ \log(n)O(n)</tex>. Так как памяти, но можно модифицировать до <tex>TO(1)</tex> - константа, то <tex>T(n). ==См. также==* [[Сортировка кучей]]* [[Быстрая сортировка]]* [[Timsort]]* [[Cортировка слиянием с использованием O(n)+\log(n)O(n1)дополнительной памяти]] ==Примечания==O(n\log(n))<references/tex> ==Источники информации==*[http://ru.wikipedia.org/wiki/Mergesort Википедия {{---}} сортировка слиянием]*[http://www.sorting-algorithms.com/merge-sort Визуализатор]*[https://ru.wikibooks.org/wiki/Примеры_реализации_сортировки_слиянием Викиучебник {{---}} Примеры реализации на различных языках программирования]