Tri Fusion

#include <stdio.h>
#include <stdlib.h>
#include "liste_ext.h"

// Affiche la liste l
void afficher( Liste l )
{
    if (est_liste_vide(l)) {
        printf( "\n" ) ;
        return ;
    }
    else {
        printf( "%i " , tete(l) ) ;
        afficher( queue(l) ) ;
    }
}

// Retourne la longueur de la liste l
int longueur( Liste l )
{
    if( est_liste_vide(l) ) return 0 ;
    else return( 1 + longueur(queue(l)) ) ;
}

Maillon *deplacer_fin( Maillon *m, Maillon *fin )
{
    if( est_liste_vide(fin) ) {
        fin = m ;
        return fin ;
    }
    fin->suiv = m;
    return fin->suiv ;
}

// l est une liste de longueur n
// Renvoie un pointeur pointant sur le debut de la 2ième moitiè de liste
Liste decouper(Liste l,int n)
{
    Liste p=l , lfin ;
    int i ;

    i=0 ;
    while( i++ < n-1 ) p= p->suiv ;
    lfin = p->suiv ;
    p->suiv = NULL ;
    return lfin ;
}

// l1 et l2 sont 2 listes triées
// Retourne une liste triée produit par la fusion de l1 et l2
Liste fusion( Liste l1, Liste l2 )
{
    Liste debut = creer_liste_vide();
    Liste l0 = creer_liste_vide() ;

    while( !(est_liste_vide(l1)) && !(est_liste_vide(l2)) ) {
        if( tete(l1)<tete(l2) ){
            l0= deplacer_fin(l1,l0) ;
            l1 = l1->suiv;
        } else{
            l0 = deplacer_fin(l2,l0) ;
            l2 = l2->suiv;
        }
        if (est_liste_vide(debut)) debut = l0 ;
    }
    while( !est_liste_vide(l1) ) {
        deplacer_fin(l1, l0) ;
        l1 = l1->suiv;
    }
    while( !est_liste_vide(l2) ) {
        deplacer_fin(l2, l0) ;
        l2 = l2->suiv;
    }

    return debut ;
}

// Effectue le trie fusion sur la liste l de longueur n
Liste tri_fusion_rec( Liste l, int n )
{
   if( n<=1 ) return l ;

   else {
        int n_debut = n/2;
        int n_fin = n - n_debut ;
        Liste l_fin ;
        l_fin = decouper(l,n_debut) ;
        l = tri_fusion_rec(l,n_debut) ;
        l_fin = tri_fusion_rec(l_fin,n_fin) ;
        return fusion(l,l_fin) ;
    }
}

// Eeeeennnnfffiiiiiiiiiinnnnnnnnnnnnnnn
Liste tri_fusion( Liste l )
{
    return tri_fusion_rec( l, longueur(l) ) ;
}