Złożoność czasowa i pamięciowa

Złożoność czasowa:

• Najlepszy, średni i najgorszy przypadek: O(n log n)
  • Tablica jest dzielona na pół około log n razy, a na każdym poziomie scalanie wymaga O(n) pracy. Czas działania nie zależy od kolejności danych wejściowych.

Złożoność pamięciowa:

• O(n)
  • W przeciwieństwie do sortowań wykonywanych w miejscu, Merge Sort tworzy nowe tablice podczas scalania, więc potrzebuje dodatkowej pamięci proporcjonalnej do rozmiaru danych wejściowych.

Podsumowanie:

• Merge Sort jest szybki i przewidywalny: O(n log n) w każdym przypadku.
• Jest stabilny, więc równe elementy zachowują swoją kolejność.
• Kompromisem jest dodatkowa pamięć O(n) używana do scalania.