import random, time

def tri_insert(liste):
    """
    Tri par insertion de la liste "liste"
    """
    n = len(liste)
    for i in range(n):
        j = i
        while j > 0 and liste[j-1] > liste[j]:
            liste[j], liste[j-1] = liste[j-1], liste[j]
            j -= 1
    return liste


def tri_fusion(liste):
    """
    fonction qui effectue un tri selon
    l'algorithme de tri par fusion
    """
    # fonction tri_fusion qui va s'appeller elle-même
    # On appelle ça une fonction récursive
    if len(liste) <= 1:
        return liste
    milieu = len(liste)//2
    liste_gauche_triee = tri_fusion(liste[:milieu])
    liste_droite_triee = tri_fusion(liste[milieu:])
    reponse = fusion(liste_gauche_triee, liste_droite_triee)
    return reponse

def fusion(liste1_triee, liste2_triee):
    # fonction qui fusionne deux listes triées
    # en une seule liste triée elle aussi
    i = 0
    j = 0
    liste_triee = []
    while i < len(liste1_triee) and j < len(liste2_triee):
        if liste1_triee[i] < liste2_triee[j]:
            liste_triee.append(liste1_triee[i])
            i += 1
        else:
            liste_triee.append(liste2_triee[j])
            j += 1
    if i < len(liste1_triee):
        liste_triee += liste1_triee[i:]
    else:
        liste_triee += liste2_triee[j:]
    return liste_triee


# création d'une liste de longueur n avec des nombres aléatoires
n = 100
liste = []
for i in range(n):
    liste.append(random.randint(0, 9))    
# chronométrage du tri:
start1 = time.time()
print('tri par insertion, liste de', len(liste), 'nombres')
print(tri_insert(liste))
duree1 = time.time() - start1
print(duree1, "secondes")
start2 = time.time()
print('tri par fusion, liste de', len(liste), 'nombres')
print(tri_fusion(liste))
duree2 = time.time() - start2
print(duree2, "secondes")