46
правок
Изменения
Нет описания правки
End
Пример работы алгоритма показан на рисунке:
[[Файл:Merge sort1.png|500px|center|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
=Время работы=
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> - время сортировки массива длины n, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex>
(<tex>O(n)</tex> - это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:
T(n) = 2T(n/2) + O(n) = 4T(n/4) + 2*O(n) = ... = 2kT(1) + kO(n).
