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