from random import *

# Tri par fusion

def fusion(left, right):
    """
    fusion(list left, list right) -> list
    Fusionne les listes triées <left> et <right> en une nouvelle liste <result>
    """
    # compléter le code en vous aidant des indications proposées:
    
    # indice pour parcourir la sous-liste de gauche

    # indice pour parcourir la sous-liste de droite

    # liste de destination
    result = []

    # tant qu'aucune des sous-listes n'est vide, il faut les parcourir
    # progressivement en comparant leurs premiers éléments et en mettant le plus
    # petit d'entre eux dans la liste de destination.


    # Une des deux sous-liste n'est pas encore vide et il faut copier tous ses
    # éléments à la fin de la liste de destination.


    return result



def TriFusion(liste):
    """
    TriFusion(list liste) -> None
    Trie la liste de nombres de manière croissante
    """
    # définition d'une fonction récursive locale utilisable qu'à l'intérieur de la fonction TriFusion
    def TriFusionInterne(liste):
        # ancrage de la récursion : lorsqu'il y a moins d'un seul élément à trier,
        # il n'y a plus rien à faire
        if len(liste) < 2:
            return liste
        else:
            # découpage en deux sous-listes de taille égale (plus ou moins 1 élément
            # pour les listes de taille impaire)
            
            # appels récursifs et fusion des résultats
            
            return # à compléter


    liste[:] = TriFusionInterne(liste)               
        

                
        
### Programme test ###

borne = 100000
n = int(input("Nombre d'éléments à trier: "))
liste = []
for i in range(n):
    liste.append(randint(0, borne))

print("La liste non triée est: ", liste, "\n")
TriFusion(liste)
print("La liste triée est: ", liste)