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>
    """
    
    # indice pour parcourir la sous-liste de gauche
    i = 0
    # indice pour parcourir la sous-liste de droite
    j = 0
    # 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.
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i = i + 1
        else:
            result.append(right[j])
            j = j + 1

    # 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.
    if i < len(left):
        result += left[i:]

    elif j < len(right):
        result += right[j:]

    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)
            mid = len(liste)//2
            left = liste[:mid]
            right = liste[mid:]
            
            # appels récursifs et fusion des résultats
            return fusion(TriFusionInterne(left), TriFusionInterne(right))

    # modification du contenu de la liste entrée
    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)