63
правки
Изменения
Нет описания правки
У нас есть два массива <tex>a</tex> и <tex>b</tex> (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив <tex>c</tex> размером <tex>|a| + |b|</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
Множество отсортированных списков с операцией <tex>merge</tex> является [[Моноид|моноидом]], <tex>\langle assorted\ list, merge, \varnothing \rangle </tex>, где <tex>\varnothing</tex> {{---}} нейтральный элемент.
Ниже приведён псевдокод процедуры слияния, который сливает две части массива <tex>a</tex> {{---}} <tex>[left; mid)</tex> и <tex>[mid; right)</tex>
</code>
===Итеративный алгоритм===
Функция сортирует все элементы массива. На <tex>i</tex> итерации мы делаем <tex>merge</tex> двух соседних групп длиной <tex>2^i</tex>.
<code style="display: inline-block">
'''function''' mergeSortIterative(a : '''int[n]'''):
*[[Cортировка слиянием с использованием O(1) дополнительной памяти]]
==СсылкиИсточники информации==
*[http://ru.wikipedia.org/wiki/Mergesort Википедия {{---}} сортировка слиянием]
*[http://www.sorting-algorithms.com/merge-sort Визуализатор]
