Сортировка слиянием
Два упорядоченных списка сливают в один за один проход: смотрят на первые еще не взятые элементы обоих списков и берут меньший. Номера i и j показывают, сколько взято из каждого списка.
Когда один список закончился, остаток другого дописывают целиком: a[i:] и b[j:].
a = [1, 4, 9]
b = [2, 3, 10, 12]
i = j = 0
result = []
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i])
i += 1
else:
result.append(b[j])
j += 1
result += a[i:] + b[j:]
print(result)
Сортировка слиянием: разделить список пополам, каждую половину отсортировать тем же способом — рекурсией, — и слить половины. Список из одного элемента уже упорядочен.
Слияние короче пишется через pop(0): он забирает из списка первый элемент. Пока оба списка не пусты, переносим в ответ меньший из первых.
На каждом уровне рекурсии сливается весь список — около n действий, а уровней около log₂ n. Для миллиона чисел это 20 уровней вместо миллиона проходов пузырька.
def merge_sort(a):
if len(a) <= 1:
return a
left, right = merge_sort(a[:len(a) // 2]), merge_sort(a[len(a) // 2:])
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
return result + left + right
print(merge_sort([5, 2, 9, 1, 7, 3]))
Итог урока. Слияние двух упорядоченных списков берет меньший из первых элементов, пока один список не кончится, а остаток дописывает целиком.
Сортировка слиянием делит список пополам, сортирует половины рекурсией и сливает их: около n · log n шагов. Знак <= при слиянии оставляет равные элементы в прежнем порядке.
В следующем уроке — двоичный поиск: как найти число в упорядоченном списке за несколько шагов.
Урок пройден
Сортировка слиянием
Выполнено заданий
Очки опыта
Обракоины
Другие уроки по теме
Следующая тема
Сортировка слиянием
Сортировка слиянием в Python: слияние двух упорядоченных списков, деление пополам и рекурсия, pop(0), устойчивость с <=. В 6 заданиях вы сольете два списка, найдете общие числа, отсортируете числа и слова слиянием, сольете несколько строк и прочитаете программу: что она выведет?