Сортировка слиянием (merge sort) в Python
В этом уроке вы реализуете сортировку слиянием по стратегии «разделяй и властвуй» с помощью рекурсивной функции.
Введение
Какую задачу это решает
Простые сортировки сильно замедляются с ростом списков: удвоение данных учетверяет работу. Сортировка слиянием делит задачу на меньшие, которые легко решить, и работа растёт лишь немного быстрее данных.
Пример из жизни
Сортировка слиянием похожа на сортировку большой стопки экзаменационных работ вместе с друзьями. Вы делите стопку пополам и раздаёте половины, а они делят свои снова, пока у каждого не окажется одна работа. Потом пары людей сливают свои отсортированные стопки, каждый раз беря меньшую верхнюю работу, пока не останется одна отсортированная стопка.
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).
Главное
if len(values) <= 1: return values- базовый случай, который останавливает рекурсию.merge_sort(values[:middle])иmerge_sort(values[middle:])сортируют две половины.- Цикл
whileберёт меньшее переднее значение изleftилиright, пока один из списков не закончится. left[left_index:]иright[right_index:]добавляют оставшиеся значения, которые уже отсортированы.<=при равенстве берёт сначала слева, что сохраняет исходный порядок равных значений.
Когда это нужно?
- Предсказуемо быстрая сортировка больших данных без плохого худшего случая.
- Сортировка связных списков или данных, которые не помещаются в память (внешняя сортировка).
- Знакомство с принципом «разделяй и властвуй», который используется во многих алгоритмах.
Когда это не нужно
- Обычный код на Python:
sorted()уже использует Timsort, настроенную смесь сортировки слиянием и вставками. - Очень мало памяти: сортировке слиянием нужно дополнительное место для слитых списков.
Визуализация: Сортировка слиянием (merge sort) в Python
O(n log n)Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.
Пример кода
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.
Упражнения для практики
Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.
- Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
- Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
- Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Частые ошибки
Забытые остатки
Когда одна половина закончилась, остаток другой теряется.
return result
return result + left[left_index:] + right[right_index:]
Закончили этот урок?
Отметьте его как изученный, чтобы следить за прогрессом.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
Все задачи