Добрый вечер. Решая задачу реализации сортировки слиянием рекурсией зашёл в тупик, вот мой код на Python:
def merge_two_list(a, b):
new = []
ai, bi = 0, 0
while ai < len(a) and bi < len(b):
aa, bb = a[ai], b[bi]
if aa <= bb:
ai += 1
new.append(aa)
else:
bi += 1
new.append(bb)
new.extend(a[ai:])
new.extend(b[bi:])
return new
def merge_sort(s):
if len(s) == 2:
return merge_two_list(s[:1], s[1:])
return merge_sort(s[:len(s) // 2]) + merge_sort(s[len(s) // 2:])
x = list(map(int, input().split()))
print(*merge_sort(x))
В функции merge_two_list реализовано слияние двух заранее отсортированных списков и с ней, как я полагаю, проблем нет. А вот с функцией merge_sort есть, на данный момент она позволяет частично отсортировать список длина которого равна 2, 4, 8, ... , 1024, ... и частично это очень частично, а именно поменять местами соседние элементы, если чётный по счёту элемент меньше предыдущего нечётного. Например, было/стало:
9 8 7 6 5 4 3 1
8 9 6 7 4 5 1 3
И на этом всё. Я никак не могу придумать, как начать снизу? Как дойдя до заведомо упорядоченных массивов длиной один, начать передавать в функцию merge_two_list уже результаты ранее отработавших вызовов этой функции? Так чтобы merge_two_list начала работать уже с отсортированными массивами не единичной длины? Условие
Код:
if len(s) == 2:
годится для старта, но никак не для продолжения, а как исправить это, придумать не выходит
Вообще рекурсия какая то очень тяжкая для меня тема, в уже прошлом году я как раз на рекурсии дизмораль словил и месяца на два забросил программирование, только в тот раз то была программа для решения судоку
