63
правки
Изменения
→Время работы
==Время работы==
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> — время сортировки массива длины <tex>n</tex>, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>
(<tex>O(n)</tex> — это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:
