Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
| Лучшая | Средняя | Худшая |
|---|---|---|
| n log n | n log n | n log n |
Рекурсивная и нерекурсивная форма сортировки слиянием имеют одинаковую вычислительную сложность, равную O(n*log(n))