63
правки
Изменения
Нет описания правки
===Слияние двух массивов===
У нас есть два массива <tex>A</tex> и <tex>B</tex> (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив <tex>C</tex> размером <tex>|A| + |B|</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
Два отсортированных списка с операцией <tex>merge</tex> являются моноидом.
Ниже приведён псевдокод процедуры слияния, который сливает две части массива <tex>A</tex> {{---}} <tex>[left; mid)</tex> и <tex>[mid; right)</tex>
'''function''' merge(a : '''int[N]'''; left, mid, right : '''int'''):
it1 = 0
it2 = 0
===Рекурсивный алгоритм===
Функция сортирует подотрезок массива с индексами в полуинтервале <tex>[left; right)</tex>.
'''function''' mergeSortRecursive(a : '''int[N]'''; left, right : '''int'''):
'''if''' left + 1 >= right
'''return'''
mergeSortRecursive(a, mid, right)
merge(a, left, mid, right)
[[Файл:Merge sort1.png|300px|Пример работы рекурсивного алгоритма сортировки слиянием]]
===Итеративный алгоритм===
Функция сортирует подотрезок массива с индексами в полуинтервале <tex>[left; right)</tex>.
'''function''' mergeSortIterative(a : '''int[N]'''; left, right : '''int'''):
'''for''' i = 1 '''to''' N, i *= 2
'''for''' j = left '''to''' right - i, j += 2 * i
