63
правки
Изменения
Нет описания правки
===Рекурсивный алгоритм===
Функция сортирует подотрезок массива с индексами в полуинтервале <tex>[left; right)</tex>.
[[Файл:Merge sort1.png|300px|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
Merge(A, left, mid, right)
===Итеративный алгоритм===
Функция сортирует подотрезок массива с индексами в полуинтервале <tex>[left; right)</tex>.
MergeSortIterative(A : '''int[1..N]'''; left, right : '''int'''):
'''for''' i = 1 '''to''' N, i *= 2
'''for''' j = left '''to''' right - i, j += 2 * i
Merge(A, j, j + i, min(j + 2 * i, right))
==Время работы==
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> — время сортировки массива длины n, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>
* [[Сортировка кучей]]
* [[Быстрая сортировка]]
*[[Cортировка Сортировка слиянием с использованием O(1) дополнительной памяти]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировка]]
[[Категория: Сортировки на сравнениях]]
