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