Давайте посмотрим, сможем ли мы решить это!
В сортировке слиянием на каждом уровне рекурсии мы делаем следующее:
- Разбить массив пополам.
- Рекурсивная сортировка каждой половины.
- Используйте алгоритм слияния для объединения двух половинок.
Так сколько сравнений делается на каждом шаге? Ну, шаг деления не делает никаких сравнений; он просто разбивает массив пополам. Шаг 2 (напрямую) не делает никаких сравнений; все сравнения выполняются рекурсивными вызовами. На шаге 3 у нас есть два массива размера n / 2, и нам нужно объединить их. Это требует не более n сравнений, поскольку каждый шаг алгоритма слияния выполняет сравнение, а затем использует некоторый элемент массива, поэтому мы не можем сделать больше, чем n сравнений.
Объединяя это вместе, мы получаем следующее повторение:
C(1) = 0
C(n) = 2C(n / 2) + n
(Как уже упоминалось в комментариях, линейный термин является более точным (n - 1), хотя это не меняет общего вывода. Мы будем использовать вышеупомянутое повторение в качестве верхней границы.)
Чтобы упростить это, давайте определим n = 2 k и перепишем это повторение в терминах k:
C'(0) = 0
C'(k) = 2C'(k - 1) + 2^k
Первые несколько терминов здесь - это 0, 2, 8, 24, .... Это выглядит примерно так: k 2 k , и мы можем доказать это по индукции. В нашем базовом случае, когда k = 0, первый член равен 0, а значение k 2 k также равно 0. Для индуктивного шага предположим, что утверждение верно для некоторого k, и рассмотрим k + 1 Тогда значение равно 2 (k 2 k ) + 2 k + 1 = k 2 k + 1 + 2 k + 1 = (k + 1) 2 k + 1 , поэтому утверждение верно для k + 1, завершающего индукцию. Таким образом, значение C '(k) равно k 2 k . Так как n = 2 k , это означает, что, предполагая, что n является совершенной степенью двойки, мы получаем, что число сделанных сравнений равно
C (n) = n lg n
Впечатляюще, это лучше , чем быстрая сортировка! Так почему же быстрая сортировка быстрее, чем сортировка слиянием? Это связано с другими факторами, которые не имеют ничего общего с количеством проведенных сравнений. Прежде всего, поскольку быстрая сортировка работает на месте, в то время как сортировка слиянием работает не на своем месте, местность ссылок не так хороша в сортировке слиянием, как в быстрой сортировке. Это такой огромный фактор, что быстрая сортировка в конечном итоге оказывается намного, намного лучше, чем сортировка слиянием на практике, поскольку стоимость промаха кэша довольно велика. Кроме того, время, необходимое для сортировки массива, учитывает не только количество сравнений. Другие факторы, такие как количество перемещений каждого элемента массива, также могут быть важны. Например, в сортировке слиянием нам нужно выделить пространство для буферизованных элементов, переместить элементы так, чтобы их можно было объединить, а затем слить обратно в массив. Эти шаги не учитываются в нашем анализе, но они определенно складываются. Сравните это с шагом разбиения быстрой сортировки, который перемещает каждый элемент массива ровно один раз и остается в исходном массиве. Эти дополнительные факторы, а не количество выполненных сравнений, доминируют во время выполнения алгоритма.
Этот анализ немного менее точен, чем оптимальный, но Википедия подтверждает, что анализ примерно n lg n и что это действительно меньше сравнений, чем в среднем случае быстрой сортировки.
Надеюсь, это поможет!