Сортировка слиянием (Merge Sort)
Сортировка слиянием (Merge sort) — один из самых быстрых алгоритмов сортировки. Многие приложения используют различные варианты сортировки слиянием в продакшене. Ранее мы обсуждали алгоритмы с квадратичным временем работы , такие как «пузырьковая» (Bubble sort) и «выбором» (Selection sort). Сортировка слиянием оказывается значительно быстрее всех квадратичных алгоритмов сортировки и работает за .
Сортировка слиянием относится к алгоритмам типа «разделяй и властвуй» (divide-and-conquer): она рекурсивно сортирует части массива и объединяет их. Основная идея — эффективно слить (merge) два уже отсортированных массива в один отсортированный массив. В ходе работы алгоритма массив разбивается на две части. Затем первая часть рекурсивно сортируется. После этого рекурсивно сортируется вторая часть. Наконец, оба отсортированных подмассива объединяются в один общий отсортированный массив:
def merge(a, b):
i, j, res = 0, 0, [] # Индексы для a и b, а также результирующий массив
while i < len(a) or j < len(b): # Пока остались элементы
ai = a[i] if i < len(a) else float('inf')
bj = b[j] if j < len(b) else float('inf')
if ai < bj: # Если a[i] < b[j], берем a[i]
res.append(ai) # Добавляем a[i] в результат
i += 1 # Переходим к следующему элементу
else: # Если a[i] >= b[j], берем b[j]
res.append(bj) # Добавляем b[j] в результат
j += 1 # Переходим к следующему элементу
return res
def merge_sort(a):
if len(a) <= 1: # Нечего сортировать
return a # Возвращаем исходный массив
l = merge_sort(a[: len(a) // 2]) # Сортируем левую часть
r = merge_sort(a[len(a) // 2:]) # Сортируем правую часть
return merge(l, r)На каждом шаге алгоритм берёт массив, делит его на две части, сортирует каждую часть отдельно и после этого сливает их в новый отсортированный массив. Обратите внимание, что все предыдущие рассмотренные алгоритмы сортировали «на месте» (in place) — изменяли исходный массив без создания нового, а сортировка слиянием каждый раз формирует новый массив. Сделать сортировку слиянием «на месте» довольно сложно. Как думаете, почему?
Давайте прогоним алгоритм на нескольких примерах:
[4, 1, -1, 0, 2, 8]
merge_sort([4, 1, -1, 0, 2, 8]):merge_sort([4, 1, -1])merge_sort([0, 2, 8])
merge_sort([4, 1, -1]):merge_sort([4])→ return[4]merge_sort([1, -1])
merge_sort([1, -1]):merge_sort([1])→ return[1]merge_sort([-1])→ return[-1]
- Back to
merge_sort([1, -1])→ return[-1, 1]
- Back to
merge_sort([4, 1, -1])→ return[-1, 1, 4]
merge_sort([0, 2, 8]):merge_sort([0])→ return[0]merge_sort([2, 8])
merge_sort([2, 8]):merge_sort([2])→ return[2]merge_sort([8])→ return[8]
- Back to
merge_sort([2, 8])→ return[2, 8]
- Back to
merge_sort([0, 2, 8])→ return[0, 2, 8]
- Back to
merge_sort([4, 1, -1, 0, 2, 8])→ return[-1, 0, 1, 2, 4, 8]
Задание
Дан массив из
n целых чисел. Требуется отсортировать его по убыванию, используя алгоритм сортировки слиянием (Merge Sort).Входные данные
В первой строке входных данных дано целое число
n (1 ≤ n ≤ 100 000).Во второй строке даны
n целых чисел ( ≤ ≤ ), разделённых пробелами, обозначающих исходный массив.Выходные данные
Программа должна вывести
n целых чисел, разделённых пробелами, расположенных в порядке убывания.Примеры
Входные данные | Выходные данные |
4
7 4 9 1 | 9 7 4 1 |
5
-4 8 2 -3 6 | 8 6 2 -3 -4 |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 10 MB