Сортировка слиянием — это разделяй и властвуй алгоритм, стабильная сортировка, работающая за гарантированное время O(n log n). Она делит массив пополам, рекурсивно сортирует каждую половину, а затем объединяет две отсортированные половины.
Идея
Одиночный элемент уже отсортирован (базовый случай). Слияние двух отсортированных списков выполняется за линейное время, и мы выполняем log n уровней слияния.
