Tri par insertion utilisant une fonction récursive en python

Question

J'essayais de mettre en œuvre un tri par insertion en utilisant une fonction récursive.

def insertion_sort(arr): 
    found=False 
    #Base case when list has only one element 
    if len(arr)==1: 
     return arr 
    else: 
    ''' 
     insert nth element in appropriate postion in a sorted list of n-1 elements 
    '''  
     partial_list=insertion_sort(arr[:len(arr)-1] 
     element=arr[-1] 
     for i in range(len(partial_list)): 
      if partial_list[i]>element: 
       index=i 
       found=True 
       break 
     if found: 
      return partial_list.insert(index,element) 
     else: 
      return partial_list.append(element) 

Mais son montrant une erreur: pour i dans la plage (len (partial_list)): TypeError: objet de type 'NoneType' n'a pas len(). Quelqu'un peut-il expliquer pourquoi partial_list est un objet de type 'None'; même si la fonction insertion_sort retourne une liste?

Answer 1

Il est évident qu'il ne retourne pas toujours une liste; au moins l'un des affirmer ou ajouter ne le fait pas.