Когда вы думаете о сортировке слиянием, вы разделяете набор (log (n)), а затем объединяете его, сортируя каждую группу (n * log (n)). В сумме это должно быть log (n) + n * log (n). Как показано на этой диаграмме: https://en.wikipedia.org/wiki/Merge_sort#/media/File:Merge_sort_algorithm_diagram.svg