Сортировка слиянием (Merge Sort) в Python

Введение

Сортировка слиянием (Merge Sort) — один из самых известных алгоритмов сортировки. Если вы изучаете информатику, Merge Sort вместе с Quick Sort, вероятно, является первым эффективным алгоритмом сортировки общего назначения, о котором вы слышали. Также классический пример алгоритма «разделяй и властвуй» (divide-and-conquer).

Merge Sort

Алгоритм сортировки слиянием работает так:

Исходный массив делится на две примерно равные части. Если массив имеет нечетное количество элементов, одна из этих «половин» на один элемент больше, чем другая.

Подмассивы делятся снова и снова на две половины, пока вы не получите массивы, которые имеют только один элемент каждый.

Затем вы объединяете пары одноэлементных массивов в двухэлементные массивы, сохраняя их в процессе. Затем эти отсортированные пары объединяются в четырехэлементные массивы и так далее до тех пор, пока не будет получен исходный отсортированный массив.

Вот визуализация сортировки слиянием:

Как вы можете видеть, тот факт, что массив не может быть разделен на равные половины, не является проблемой, 1 просто «ждет», пока не начнется сортировка.

Существует два основных способа реализации алгоритма сортировки слиянием, один из которых использует подход сверху вниз, как в примере выше, и именно так чаще всего используется.

Другой подход, то есть восходящий, работает в противоположном направлении, без рекурсии (работает итеративно) — если наш массив имеет N элементов, мы делим его на N подмассивов одного элемента и сортируем пары смежных одноэлементных массивов, затем сортируем соседние пары двухэлементных массивов и т. д.

Примечание: подход снизу вверх обеспечивает интересную оптимизацию. Но мы будем реализовывать нисходящий подход, так как это более простые и интуитивно понятные пары с тем фактом, что между ними нет реальной разницы во временной сложности без особых оптимизаций.

Основная часть обоих этих подходов заключается в том, как мы объединяем (merge) два меньших массива в больший массив. Это сделано довольно интуитивно, скажем, мы рассмотрим последний шаг в нашем предыдущем примере. У нас есть массивы:

• A: 4 7 9 10
• B: 1 3 6
• sorted: empty

Первое, что мы сделаем, это посмотрим на первый элемент обоих массивов. Мы находим тот, который меньше, в нашем случае это 1, так что это первый элемент нашего отсортированного массива, и мы продвигаемся вперед в массиве B:

• A:  4 7 9 10
• B: 1 3 6
• sorted: 1

Затем мы смотрим на следующую пару элементов 4 и 3; 3 меньше, поэтому мы помещаем его в наш отсортированный массив и перемещаемся вперед в массиве B. Конечно, мы не перемещаемся вперед в массиве A, и мы сохраняем наш указатель на 3 для будущих сравнений:

• A: 4 7 9 10
• B: 1 3 6
• sorted: 1 3

Используя ту же логику, мы перемещаемся по остальным и получаем массив {1, 3, 4, 6, 7, 9, 10}.

Возможны два особых случая:

• Оба подмассива имеют одинаковый элемент. Мы можем двигаться вперед в любом из них и добавить элемент в отсортированный массив. Мы можем технически продвинуться вперед в обоих массивах и добавить оба элемента в отсортированный массив, но это потребует особого поведения, когда мы встретим одинаковые элементы в обоих массивах.
• Мы «исчерпали» элементы в одном подмассиве. Например, у нас есть массив с {1, 2, 3} и массив с {11, 12, 13}. Ясно, что мы пройдемся по всем элементам первого массива, не продвигаясь вперед ни разу во втором. Всякий раз, когда у нас заканчиваются элементы в подмассиве, мы просто добавляем элементы второго за другим.

Имейте в виду, что мы можем сортировать по своему усмотрению — этот пример сортирует целые числа в порядке возрастания, но мы можем так же легко сортировать в порядке убывания или сортировать пользовательские объекты.

Реализация

Мы будем реализовывать сортировку слиянием на массивах целых чисел (обычно используемых для представления сортировки).

Мы реализуем алгоритм сортировки слиянием, используя подход сверху вниз.

Сортировка массивов

Начнем с простой части. Основная идея алгоритма состоит в том, чтобы разделить (под) массивы пополам и отсортировать их рекурсивно. Мы будем продолжать делать это как можно больше, то есть до тех пор, пока не получим подмассивы, которые имеют только один элемент:

import operator

def merge_sort(L, compare=operator.lt):
    if len(L) < 2:
        return L[:]
    else:
        middle = int(len(L) / 2)
        left = merge_sort(L[:middle], compare)
        right = merge_sort(L[middle:], compare)
        return merge(left, right, compare)

Последним вызовом метода merge мы гарантируем, что все деления произойдут до того, как мы начнем сортировку.

Создадим функцию merge():

def merge(left, right, compare):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if compare(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while i < len(left):
        result.append(left[i])
        i += 1
    while j < len(right):
        result.append(right[j])
        j += 1
    return result

Теперь давайте проверим нашу программу:

array = [78, 41, 4, 27, 3, 27, 8, 39, 19, 34, 6, 41, 13, 52, 16]
merge_sort(array)

И результат:

[3, 4, 6, 8, 13, 16, 19, 27, 27, 34, 39, 41, 41, 52, 78]

Заключение

Merge Sort — эффективный алгоритм сортировки общего назначения. Его основным преимуществом является надежное время выполнения алгоритма и его эффективность при сортировке больших массивов. В отличие от быстрой сортировки, он не зависит от каких-либо неудачных решений, которые приводят к плохому времени выполнения.

Одним из основных недостатков является дополнительная память, которую сортировка слиянием использует для хранения временных копий массивов перед их объединением. Тем не менее, Merge Sort является отличным, интуитивно понятным примером для ознакомления будущих инженеров-программистов с подходом «разделяй и властвуй».

Источники используемые для написания статьи:  
Olivera Popović — Merge Sort in Python
https://stackoverflow.com/questions/18761766/mergesort-with-python