Изменения

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

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

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

===Слияние двух массивов===У нас есть два массива <pretex>a</tex> и <tex>b</ слияние двух массивов с помощью временногоmergetex> (array aфактически это будут две части одного массива, int leftно для удобства будем писать, int middle, int rightчто у нас просто два массива) // left - левая граница, right - правая, middle - середина array b = a[middle + 1, right]; i = left, j = middle + 1, k = 0; array temp; while i . Нам надо получить массив <= middle and j tex>c<= right temp[k++] = (a[j] /tex> размером < b[i]) ? tex>|a[j| ++] : |b[i++]; while i |<= middle temp[k++] = b[i++]; while j <= right 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Моноид|Пример работы рекурсивного алгоритма сортировки слияниеммоноидом]]Функция сортирует участок массива от элемента с номером left до элемен­та с номером right:, где нейтральным элементом будет пустой список.

Ниже приведён псевдокод процедуры слияния, который сливает две части массива <tex>a</tex> {{---}} <tex>[left; mid)</tex> и <tex>[mid; right и )</tex><code style="display: inline-block"> '''function''' merge(a : '''int[n]'''; left — правая и левая граница массива, middle — середина.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[it1 + it2] = a[left + it1] it1 += 1 '''while''' mid + it2 < right result[it1 + it2] = a[mid + it2] it2 += 1 '''for''' i = 0 '''to''' it1 + it2 a[left + i] = result[i]</code>

Условие выхода — если массив стал состоять из 1 элемента===Рекурсивный алгоритм===Функция сортирует подотрезок массива с индексами в полуинтервале <tex>[left; right)</tex>.<precode style="display: inline-block">sort '''function''' mergeSortRecursive(array a, : '''int [n]'''; left, right : '''int right'''): middle '''if''' left + 1 >= right / 2 if middle = '''return''' mid = (left + right ) / 2 return sort mergeSortRecursive(a, left, middlemid) sort mergeSortRecursive(a, middle + 1mid, right) merge(array a, left, middlemid, right)</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>

==Восходящая сортировка слияниемВремя работы==[[Файл:mergenonrecЧтобы оценить время работы этого алгоритма, составим рекуррентное соотношение.png|300px|right|thumb|Пример работы восходящей Пускай <tex>T(n)</tex> {{---}} время сортировки массива длины <tex>n</tex>, тогда для сортировки слиянием]]справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>Помимо рекурсивного алгоритма существует и альтернативный.Пример работы алгоритма показан <tex>O(n)</tex> {{---}} время, необходимое на рисунке: # Выделим память размером с занимаемой памяти исходного массива.# Попарно сравним элементыто, записывая во временную память.# Поменяем указатели временного и исходного чтобы слить два массивадлины <tex>n</tex>.# Выполним слияние "кусочков" размером два.# Повторяем до тех пор, пока не сделаем единый кусок.# Удаляем временный массив.Распишем это соотношение:

Процедуру слияния надо будет изменить, так, что-бы она записывала результат в результирующий массив (mas1)<pretex>sortT(array * mas, int elementsAmountn) array * mas1 = new array[elementsAmount]; for2T(int size = 1; size < elementsAmount; size *= n/2) { int start +O(n)= 0; for4T(; n/4)+2O(start + sizen) < elementsAmount; start += size * 2\dots=T(1) merge(mas + start, mas + start, mas + start + size, mas + start + size + min\log(size,elementsAmount - start - sizen)O(n); for=O(; start < elementsAmount; ++startn\log(n)) mas1[start] = mas[start]; array * temp = mas1; mas1 = mas; mas = temp; delete[] mas1;</pretex>.

==Время работыСравнение с другими алгоритмами==Чтобы оценить время работы этого алгоритмаДостоинства:* устойчивая,* можно написать эффективную [[Многопоточная сортировка слиянием|многопоточную сортировку слиянием]],* сортировка данных, составим рекуррентное соотношение. Пускай расположенных на периферийных устройствах и не вмещающихся в оперативную память<texref>T(n)[http://en.wikipedia.org/wiki/External_sorting Wikipedia {{---}} External sorting]</texref> — время сортировки массива длины n, тогда для сортировки слиянием справедливо .Недостатки:* требуется дополнительно <tex>T(n)=2T(n/2)+O(n)</tex> <br>(памяти, но можно модифицировать до <tex>O(n1)</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>.