Алгоритмы на Python

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

В этом уроке вы реализуете сортировку слиянием по стратегии «разделяй и властвуй» с помощью рекурсивной функции.

  • Средний
  • Чтение: 3 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

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

Пример из жизни

Сортировка слиянием похожа на сортировку большой стопки экзаменационных работ вместе с друзьями. Вы делите стопку пополам и раздаёте половины, а они делят свои снова, пока у каждого не окажется одна работа. Потом пары людей сливают свои отсортированные стопки, каждый раз беря меньшую верхнюю работу, пока не останется одна отсортированная стопка.

От сортировки работ к коду
if len(values) <= 1:📄 Одна работа уже отсортирована
merge_sort(values[:middle])✂️ Разделить стопку и отсортировать каждую половину
left[left_index] <= right[right_index]🤝 Слияние: взять меньшую верхнюю работу
result + left[left_index:] + right[right_index:]📚 Добавить то, что осталось от другой стопки
Делите до отдельных элементов, потом сливайте отсортированные стопки обратно.
Одним предложением

Сортировка слиянием делит список пополам, рекурсивно сортирует каждую половину и сливает две отсортированные половины; это занимает время O(n log n).

Главное

  1. if len(values) <= 1: return values - базовый случай, который останавливает рекурсию.
  2. merge_sort(values[:middle]) и merge_sort(values[middle:]) сортируют две половины.
  3. Цикл while берёт меньшее переднее значение из left или right, пока один из списков не закончится.
  4. left[left_index:] и right[right_index:] добавляют оставшиеся значения, которые уже отсортированы.
  5. <= при равенстве берёт сначала слева, что сохраняет исходный порядок равных значений.

Когда это нужно?

  • Предсказуемо быстрая сортировка больших данных без плохого худшего случая.
  • Сортировка связных списков или данных, которые не помещаются в память (внешняя сортировка).
  • Знакомство с принципом «разделяй и властвуй», который используется во многих алгоритмах.

Когда это не нужно

  • Обычный код на Python: sorted() уже использует Timsort, настроенную смесь сортировки слиянием и вставками.
  • Очень мало памяти: сортировке слиянием нужно дополнительное место для слитых списков.

Визуализация: Сортировка слиянием (merge sort) в Python

O(n log n)

Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.

Пример кода

Запустить код →
main.py
def merge_sort(values):
    if len(values) <= 1:
        return values
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    result = []
    left_index = right_index = 0
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1
    return result + left[left_index:] + right[right_index:]

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
Получить кнопку запуска для этого примера

Результат выполнения

[3, 9, 10, 27, 38, 43, 82]

Разбор кода

Рекурсивная функция делит список, пока в каждом куске не останется по одному элементу, ведь список из одного элемента всегда отсортирован. Затем цикл while сливает два подсписка, каждый раз забирая меньший из двух первых элементов. Алгоритм всегда работает за O(n log n) и требует O(n) дополнительной памяти.

Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

Частые ошибки

Забытые остатки

Когда одна половина закончилась, остаток другой теряется.

Ошибка
return result
Исправление
return result + left[left_index:] + right[right_index:]

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Попрактикуйтесь на задаче

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

Все задачи