from random import seed, randint, shuffle

def tri_split_merge(L) :
    """ TRI SPLIT-MERGE avec 2 fonctions imbriquées """
    def my_split(L) :
        choix=True              # on met dans L1, sinon dans L2 
        L1=[]; L2=[] ; N =len(L)
        i=0
        while i < N :
            crt=L[i]
            if choix : L1.append(crt)
            else : L2.append(crt)
            i +=1
            # voyons si on a une séquence Descendante
            while i < N and L[i] >= crt :
                crt=L[i]
                if choix : L1.append(crt)
                else : L2.append(crt)
                i +=1
                
            choix = not choix
            
        return(L1,L2)
    
    #---------------------  
    def my_merge(L1,L2) :
        N1=len(L1)
        N2=len(L2)
        L=[]; i,j=0,0
        while(i < N1 and j < N2) :
            if L1[i] <= L2[j] : 
                L.append(L1[i]) 
                i+=1
            else :
                L.append(L2[j]) 
                j+=1
        L.extend(L1[i:])    # Ajouter le reste de L1 (s'il y en a) à L
        L.extend(L2[j:])    # Ajouter le reste de L2 (s'il y en a) à L
        return L
        
    # Fonction tri_split_merge
    while True :
        (L1,L2) = my_split(L)
        if (L2==[]) : break # Fini
        L=my_merge(L1,L2)  
    return L
        
# programme principal -----------------------------------------------
seed() # initialise le generateur de nombres aleatoires
N=10
L = [randint(2, N*4) for i in range(N)] # construction de la liste
print("Avant le tri, liste = {}".format(L))
L=tri_split_merge(L)
print("Après le tri, liste = {}".format(L))

""" Deux Traces
Avant le tri, liste = [9, 17, 12, 24, 36, 26, 35, 25, 5, 31]
Après le tri, liste = [5, 9, 12, 17, 24, 25, 26, 31, 35, 36]

Avant le tri, liste = [30, 14, 2, 11, 5, 15, 5, 21, 29, 31]
Après le tri, liste = [2, 5, 5, 11, 14, 15, 21, 29, 30, 31]
"""