Меня смущает приведенное ниже объяснение в одном из поисковых запросов Google для сортировки слиянием
T(n) = 2T(n/2) + (n-1) Это уравнение левой стороны, если вы решите, разрешится к n*log(n)
Здесь 2T(n/2) правильно, потому что каждый раз мы разбиваем массив из n элементов на 2 части ... и разбиваем их дальше, пока не достигнем массива с одним элементом.
В части слияния, в большинство, мы сравниваем n элементов в худшем случае. Но, как показано в приведенном выше уравнении, это n-1. Не могу понять, почему это n-1.