Аналіз часової та просторової складності сортування злиттям
The Часова складність Сортування злиттям є O(n log n) в обох середній і найгірші випадки . Космічна складність Сортування злиттям є O(n) . 
| Аспект | Складність |
|---|---|
| Часова складність | O(n log n) |
| Космічна складність | O(n) |
Аналіз тимчасової складності сортування злиттям:
Розглянемо такі терміни:
T(k) = час, витрачений на сортування k елементів
M(k) = час, витрачений на об’єднання k елементів
Отже, це можна написати
T(N) = 2 * T(N/2) + M(N)
= 2 * T(N/2) + константа * N
Ці N/2 елементи далі розділені на дві половини. Так,
T(N) = 2 * [2 * T(N/4) + константа * N/2] + константа * N
= 4 * T(N/4) + 2 * N * константа
. . .
= 2 k * T(N/2 k ) + k * N * константа
Його можна розділити максимум, поки не залишиться один елемент. Отже, тоді N/2 k = 1. k = журнал 2 Н
T(N) = N * T(1) + N * log 2 N * постійна
= N + N * log 2 Н
Тому часова складність є O(N * log 2 N) .
Отже, у найкращому, гіршому та середньому випадку часова складність однакова.
Аналіз просторової складності сортування злиттям:
Сортування злиттям має складність простору з O(n) . Це тому, що він використовує допоміжний масив розміру п щоб об’єднати відсортовані половини вхідного масиву. Допоміжний масив використовується для зберігання об’єднаного результату, а вхідний масив перезаписується відсортованим результатом.
