Time and Space Complexity

Временная сложность:

• Лучший, средний и худший случаи: O(n log n)
  • Массив делится пополам примерно log n раз, и на каждом уровне выполняется работа O(n) по слиянию. Время выполнения не зависит от порядка входных данных.

Пространственная сложность:

• O(n)
  • В отличие от сортировок «на месте» (in-place), сортировка слиянием (Merge Sort) создает новые массивы во время слияния, поэтому ей требуется дополнительная память, пропорциональная размеру входных данных.

Итог:

• Сортировка слиянием быстрая и предсказуемая: O(n log n) в любом случае.
• Она стабильна, поэтому равные элементы сохраняют свой порядок.
• Компромиссом является дополнительная память O(n), которую она использует для слияния.