Рекурсивно сортировать два отдельных списка

Question

Определить рекурсивную функцию с именем sort; он передается любым неупорядоченным списком; он возвращает новый список (не изменяя аргумент), который содержит каждое значение в списке аргументов, но не в порядке убывания.

Например, вызов sort([4,5,3,1,6,7,2]) бы назвать своего рода рекурсивно по спискам [4,5,3] и [1,6,7,2], возвращая списки [3,4,5] и [1,2,6,7] соответственно, которые, когда слиты будет возвращать список [1,2,3,4,5,6,7].

Обратите внимание, что если длина списка ровная, оба подписок будут иметь одинаковый размер ; когда длина списка нечетна, естественно разделить ее на два списка, первый из которых имеет меньшее значение, чем второе.

Функция начинается так:

def sort(l): 

Я знаю, как отделить л в два списка, например [4,5,3,1,6,7,2], я разделить их на [4,5,3] и [1,6,7,2]. Но я действительно не знаю, как рекурсивно сортировать каждую половину, когда функция sort имеет только один аргумент l.

Может кто-нибудь рассказать, как это сделать? Спасибо.

Answer 1

Я дал ему ход, и он работает. Как сказал TobiasR, это сортировка слияния. Если вы хотите лучше объяснить, как это работает, я бы проверил this video on merge sorts by Harvard University. Во всяком случае, это код для него:

def sort(l): 
    if len(l)==2: 
     if l[0]<l[1]: 
      return l #return list as it is 
     return l[::-1] #return reversed list 
    elif len(l)==1: 
     return l 
    l_1=sort(l[:len(l)//2]) # cut the list in half 
    l_2=sort(l[len(l)//2:]) 
    l_out=[] 
    while True: 
     if not l_1: #check l1 isn't empty 
      l_out+=l_2 
      break; 
     elif not l_2: #check l2 isn't empty 
      l_out+=l_1 
      break; 
     if l_1[0]<l_2[0]: #put the smallest item in the list 
      l_out.append(l_1.pop(0)) 
     else: 
      l_out.append(l_2.pop(0)) 
    return l_out