На этом шаге мы рассмотрим особенности рекурсивной реализации этого алгоритма.

Алгоритм сортировки слиянием - один из широко используемых примеров для демонстрации возможностей подхода "разделяй и властвуй". В то время как многие алгоритмы сортировки работают в худшем случае за время Ο(n²), алгоритм сортировки слиянием работает за время Θ(n log n). Иными словами, его вычислительная эффективность сулит лучшие перспективы.

Размер задачи - длина списка (n). Наименьшие экземпляры задачи возникают при n ≤ 1, когда алгоритм просто должен вернуть входной список. В рекурсивном условии алгоритм разбивает задачу путём деления входного списка на две половины, порождая тем самым две разные подзадачи (примерно) в половину размера исходной. В следующей схеме приводится конкретный пример рекурсивного процесса осмысления будущего алгоритма:

Рис.1. Алгоритм сортировки слиянием

Рекурсивное условие здесь сложнее, чем в предыдущих примерах, так как окончательный сортированный список не может быть создан простой операцией (например, суммированием, вычислением максимума двух чисел, соединением двух списков и т. д.). В этом случае необходимо решить новую задачу слияния (объединения) решений подзадач. В частности, для получения итогового сортированного списка рекурсивное условие должно "слить" два сортированных списка (выходы двух подзадач). В примере 6.2 приводится компактная реализация метода сортировки слиянием в предположении, что решающая эту задачу функция merge (см. ниже) уже реализована. Отметим лёгкость восприятия кода и простоту алгоритма, который в точности отвечает стратегии "разделяй и властвуй".

Пример 6.2. Метод сортировки слиянием

1
2
3
4
5
6
7
8

def merge_sort(a):
    n = len(a)
    if n <= 1:
        return a
    else:
        a1 = merge_sort(a[0:n // 2])     
        a2 = merge_sort(a[n // 2:n])
        return merge(a1, a2)

Оценка времени выполнения этого алгоритма:

            1,              если n ≤ 1
    T(n) = 
            2T(n/2) + f(n), если n > 1

где мы также предположили, что разделение списка требует постоянного числа операций. Иными словами, мы решили, что a[0:n//2] и a[n//2:n] можно получить за время Θ(1). Кроме того, f(n) оценивает количество операций, необходимых методу слияния для объединения двух сортированных списков (приблизительно) из n/2 элементов. В этом случае, согласно основной теореме (3.28), если бы f(n) была линейной функцией, то алгоритм сортировки слиянием работал бы за (оптимальное) время порядка Θ(n log n). Скоро мы увидим, что на самом деле задачу слияния можно решить за линейное время. Вообще, сталкиваясь с подобной задачей, разработчики алгоритма всегда стремятся создать наиболее эффективную комбинацию методов, снижающую издержки алгоритма "разделяй и властвуй".

Входы задачи слияния - два сортированных списка a и b с длинами n_a и n_b соответственно. Выход - другой сортированный список длины n = n_a + n_b. Можно считать, что размер задачи - это количество операций, необходимых рекурсивному алгоритму, чтобы "спуститься" до тривиального решения. При таком сценарии размер задачи будет m = min(n_a, n_b), поскольку если один из списков пуст, то решением задачи будет, очевидно, второй список. Это - начальные условия. Для рекурсивного условия можно использовать следующую схему с подсписками из предыдущего примера:

Декомпозиция уменьшает размер задачи на 1 за счёт отбрасывания наименьшего элемента в обоих списках. Естественно, он может оказаться в начальной позиции списков, поскольку они отсортированы по возрастанию. В примере наименьший элемент (3) - первый в первом входном списке. Очевидно, что рекурсивное условие должно просто присоединить этот элемент к результату подзадачи. В примере 6.3 приведён соответствующий код. Оценка времени его выполнения характеризуется функцией

            1,          если m = 0
    T(m) = 
            T(m-1) + 1, если m > 1

в предположении, что хвост списка (то есть х[1:]) можно получить за конечное время. Так как его нерекурсивное выражение - T(m) = m + 1, функция слияния выполняется за линейное время от m и от n тоже. А это значит, что алгоритм сортировки слиянием работает за время Θ(n log n).

Пример 6.3. Метод для слияния двух сортированных списков

1
2
3
4
5
6
7
8
9
10
11

# Списки a и b отсортированы по возрастанию.    
def merge(a, b):
    if a == []:
        return b
    elif b == []:
        return a
    else:
        if a[0] < b[0]:
            return [a[0]] + merge(a[1:], b)
        else:
            return [b[0]] + merge(a, b[1:])

Архив с файлом можно взять здесь.

На следующем шаге мы рассмотрим алгоритм быстрой сортировки.

Предыдущий шаг Содержание Следующий шаг