Programme tri_fusion.py

def fusion(a,b):
    """fonction fusionnant les deux listes a,b supposees triees,
    retourne une liste triee.
    
    a chaque passage dans la boucle, on ajoute un element
    provenant de l'une des deux listes, on conserve pour ces 
    deux listes l'indice de l'element suivant a inserer 
    dans la liste resultat : k pour la liste a, n pour la liste b
    
    a chaque passage, on choisit le plus petit, 
       si c'est celui de la liste a, on incremente k,
       si c'est celui de la liste b, on incremente n
       
       il faut faire attention lorsqu'on a ajouter les elements d'une liste,
       parce que l'indice k ou n ne designe aucun element, de plus,
       cela signifie qu'on doit ajouter les derniers elements
       de l'autre liste.
    """
    c=[]
    l=len(a)+len(b)
    k=0
    n=0
    while len(c)<l:
        if k==len(a):     # liste a terminee
            c.extend (b[n:])
        elif n==len(b):   # liste b terminee
            c.extend(a[k:])
        elif a[k]<b[n]:   # element de la liste plus petit
            c.append(a[k])
            k=k+1
        else :            # element de la liste b plus petit
            c.append(b[n])
            n=n+1
    return c

def tri(l):
    """effectue le tri par fusion, coupe la liste en deux,
    appelle recursivement le tri par fusion sur chacun des
    deux morceaux puis assemble les deux listes triees
    
    le cout de cette fonction depend de n : 
        - fusionner de liste a un cout en O(n)
        - on appelle la fonction fusion sur :
                - le tableau initial : n elements
                - sur deux moities : 2 * n/2
                - sur quarts quarts : 4 * n/4
                - ...
                - sur n/2 sous-liste de 2 elements : n/2 * 2
    le cout du tri par fusion est n * autant de fois
    qu'on peut divisier n par 2 : O(n log (n))"""
    if len(l)>1:
        n=int(len(l)/2)
        a=l[n:len(l)]  # premiere moitie
        b=l[0:n]       # seconde moitie
        tri(a)         # tri de la premier moitie
        tri(b)         # tri de la seconde moitie
        t=fusion(a,b)  # fusion des deux listes triees
        for i in range(0,len(l)):  # on recopie la liste triee dans la 
            l[i]=t[i]              # liste initiale
        # on ne peut pas ecrire que :
        #   l = t
        # car dans ce cas, on sert du nom l pour stocker autre chose
        # que la liste l, cette ligne attribuerait le nom l a une autre liste
        # qui serait perdue a la fin de la fonction

k=[2,8,9,5,15,4,56,78,85,15,45,3]
print "non triee ", k
tri(k)
print "triee ",k