Что такое сортировка слиянием?

Сортировка слиянием (Merge Sort) — это один из самых эффективных алгоритмов сортировки, работающий по принципу "разделяй и властвуй". В Python этот метод используется как один из основных для сортировки больших коллекций данных, тогда как для небольших массивов обычно применяют сортировку вставками.

Ключевые особенности алгоритма

  1. Рекурсивная природа: алгоритм естественным образом реализуется через рекурсию, последовательно разделяя массив на меньшие части.

  2. Стабильность: сохраняет порядок равных элементов.

  3. Предсказуемая производительность: всегда работает с одинаковой скоростью независимо от входных данных.

Сложность алгоритма

Сортировка слиянием имеет линейно-логарифмическую сложность:

  • В худшем случае: O(n log n)

  • В лучшем случае: O(n log n)

  • Средний случай: O(n log n)

Это делает алгоритм значительно эффективнее квадратичных сортировок (O(n²)) при работе с большими объемами данных.

Как работает сортировка слиянием?

Процесс состоит из двух основных этапов:

  1. Разделение:

    • Массив рекурсивно делится пополам

    • Процесс продолжается, пока не останутся подмассивы из одного элемента

  2. Слияние:

    • Отсортированные подмассивы объединяются в новый отсортированный массив

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

def merge_sort(list_):
        if len(list_) > 1:
            mid = len(list_) // 2
            left =  list_[:mid]
            rigth = list_[mid:]
            merge_sort(left)
            merge_sort(rigth)
            left_lst = 0
            rigth_lst = 0
            list_lst = 0
            while len(left) > left_lst and len(rigth) > rigth_lst:
                if left[left_lst] >= rigth[rigth_lst]:
                    list_[list_lst] = rigth[rigth_lst]
                    rigth_lst  += 1
                else:
                    list_[list_lst] = left[left_lst]
                    left_lst += 1
                list_lst += 1
            while len(left) > left_lst:
                list_[list_lst] = left[left_lst]
                left_lst += 1
                list_lst += 1
            while len(rigth) > rigth_lst:
                list_[list_lst] = rigth[rigth_lst]
                rigth_lst += 1
                list_lst += 1
            return list_

list_ = [4, 7, 8, 3, 5]
print(merge_sort(list_))

Преимущества сортировки слиянием

  1. Высокая производительность на больших массивах

  2. Стабильность работы — одинаковое время выполнения для любых входных данных

  3. Параллелизуемость — подмассивы можно сортировать независимо

  4. Внешняя сортировка — может работать с данными, не помещающимися в оперативную память