Рекурсивная программа Python для объединения трех отсортированных списков

Question

Напишите чисто рекурсивную функцию Python с именем Merge3, которая принимает в качестве входных данных три списка чисел, каждый из которых отсортирован в порядке возрастания, и выводит один отсортированный список, объединяя элементы из трех списков в правильном порядке возрастания. Например, Merge3([1,2,72,108],[3,4,94,103],[45,67,456]) должен вернуть список [1,2,3,4,45,67,72,94,103,108,456].

Мне удалось написать версию для двух списков, но я изо всех сил пытаюсь придумать компактный способ сделать это для трех списков. Смотрите мой пример ниже:

def Merge2(A, B):
  if A == []:
    return B
  if B == []:
    return A
  if A != [] and B != []:
    if A[0] > B[0]:
      return [B[0]] + Merge(A, B[1:])
    else:
      return [A[0]] + Merge(A[1:], B)

print(Merge2([1, 2, 6, 7],[3, 4, 8, 9]))

Есть ли простой способ сделать это для трех списков, которые мне не хватает? Я чувствую, что потребуется много дополнительных проверок, которые сделают программу довольно длинной. Можете ли вы придумать краткий способ сделать это для трех списков?

Answer 1

ответ Яноша за Merge3 идеален. Я действительно хотел предложить вам улучшение Merge2 однако -

def Merge2(A, B):
  if not A:
    return B
  elif not B:
    return A
  elif A[0] > B[0]:
    return [B[0]] + Merge2(A, B[1:])
  else:
    return [A[0]] + Merge2(A[1:], B)

print(Merge2([1, 2, 6, 7],[3, 4, 8, 9, 11, 13]))
# [1, 2, 3, 4, 6, 7, 8, 9, 11, 13]

Answer 2

Простой способ решить эту проблему - повторно использовать Merge2, которое у вас уже есть:

def Merge3(A, B, C):
    return Merge2(Merge2(A, B), C)