Extrait de la doc python :

list.insert(i, x)

Insert an item at a given position. The first argument is the index of the element before which to insert, so a.insert(0, x) inserts at the front of the list, and a.insert(len(a), x) is equivalent to a.append(x).

list.pop([i])

Remove the item at the given position in the list, and return it. If no index is specified, a.pop() removes and returns the last item in the list. (The square brackets around the i in the method signature denote that the parameter is optional, not that you should type square brackets at that position. You will see this notation frequently in the Python Library Reference.)

On suppose la liste T triée en ordre croissant. La fonction insere(T, elt) proposée insére le nouvel élément elt au bon indice dans la liste T de façon à ce que cette liste augmentée de cet élément soit encore triée (en ordre croissant).

Principe du "tri insertion".

L est la liste à trier, T initialement vide sera la liste retournée.

1. Si la liste L est vide, retourner T.
2. Sinon :
   • Retirer un élément de la liste L.
   • Insérer cet élément à la bonne place dans la liste T.
   • Reprendre au point 1.

from random import randint


def insere(T, elt, k = 0) :
	if T == [] or (k == 0 and elt <= T[0]) :  T.insert(0,elt)
	elif elt > T[-1] : T.append(elt)
	else :
		if ( T[k-1] <= elt <= T[k] ) :  T.insert(k,elt)
		else : return insere(T, elt, k+1)
	
 
		
		
def tri(L, T= []) :
	if L == [] : return T
	else : 
		a = L.pop()
		insere(T, a)
		return tri(L, T)
	 
	
# création d'une liste d'entiers au hasard
# pour tester la fonction de tri :
L = [ randint(1,100) for j in range(randint(0,10))]
 		
 			
print(L)


print(tri(L))