Изменения

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

==Принцип работы==[[Файл:Merge-sort-exampleitearative.jpgpng|300px|right|300px|thumb|Пример работы процедуры слияния.итеративного алгоритма сортировки слиянием]]Этот алгоритм использует принцип «разделяй и властвуй». Этот принцип заключается в том, что исходная задача разбивается на подзадачи меньшего размера, а потом они решаются рекурсивным методом или же конкретно, если их размер мал. Потом из решения объединяются и получается решение основной (исходной) задачи.

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

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

У нас есть два массива <tex>Aa</tex> и <tex>Bb</tex>(фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив <tex>Cc</tex> размером <tex>|Aa| + |Bb|</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.

Ниже приведён псевдокод процедуры слияния, который сливает две части массива <pretex>a</tex> {{---}} <tex>[left; mid)</tex> и <tex>[mid; right)</ слияние двух частей одного массива с помощью временногоtex>// left <code style="display: inline- левая граница, right - правая, middle - серединаblock"> '''function''' merge(array a, : '''int [n]'''; left, int middlemid, right : '''int right''') : i it1 = left, j = middle, k 0 it2 = 0; array temp = new array result : '''int[a.size()right - left];''' '''while i ''' left + it1 <= middle mid '''and j ''' mid + it2 < right '''if (''' a[jleft + it1] < a[imid + it2]) temp result[k+it1 +it2] = a[jleft +it1] it1 +];= 1 '''else''' temp result[k+it1 +it2] = a[imid +it2] it2 +];= 1 '''while i ''' left + it1 <= middlemid temp result[k+it1 +it2] = a[ileft +it1] it1 +];= 1 '''while j ''' mid + it2 < right temp result[k+it1 +it2] = a[jmid +it2] it2 +];= 1 '''for (int t ''' i = 0; t != k; t+'''to''' it1 +)it2 a[tleft + i] = tempresult[t];// в конце a[1..ki] это будет отсортированный массив</precode>

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

right и left — правая и левая граница массива===Итеративный алгоритм===При итеративном алгоритме используется на <tex>O(\log n)</tex> меньше памяти, middle — серединакоторая раньше тратилась на рекурсивные вызовы.<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>

Условие выхода — если массив стал состоять из 1 элемента==Время работы==Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение.Пускай <pretex>sortT(array an)</tex> {{---}} время сортировки массива длины <tex>n</tex>, int left, int rightтогда для сортировки слиянием справедливо <tex>T(n) middle = 2T(left + right) n/ 2; if middle == right return; sort)+O(a, left, middlen);</tex> <br> sort <tex>O(a, middle, rightn); merge(array a</tex> {{---}} время, leftнеобходимое на то, middle, right);чтобы слить два массива длины <tex>n</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>2O(n)</tex> <tex>См. также=</tex> <tex>...</tex> <tex>=</tex> <tex>2^kT* [[Сортировка кучей]]* [[Быстрая сортировка]]* [[Timsort]]* [[Cортировка слиянием с использованием O(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>.