Хорошо, я знаю, что Mergesort имеет время тэты наихудшего случая (NlogN), но его накладные расходы высоки и проявляются в нижней части дерева рекурсии, где выполняются слияния. Кто-то предложил остановить рекурсию, как только размер достигнет K, и переключиться на сортировку вставкой в этой точке. Мне нужно доказать, что время работы этого модифицированного рекуррентного отношения равно тета (NK + Nlog (N / k))? Я не понимаю, как подойти к этой проблеме.