Exercice 17 - Tri fusion

Le tri par fusion se fait en coupant un tableau en deux sous-tableaux de tailles égales à un élément près, en triant récursivement les deux sous-tableaux puis en interclassant leurs éléments. Ecrire en C une fonction de tri fusion de listes chaînées. Vous prendrez garde à ne pas recopier les maillons, et à seulement modifier le chaînage. Vous utiliserez les sous-programmes énoncés ci-après. Notez bien le type des paramètres.

• void split(linkedList* source, linkedList* dest1, linkedList* dest2), répartit les maillons de source dans dest1 et dest2.
• void merge(linkedList* source1, linkedList* source2, linkedList* dest, int (*inf) (void*, void*)), interclasse les listes source1 et source2 et place le résultat dans la liste dest. Le fonction pointée par $f$ retourne $1$ si la clé premier paramètre est inférieur à la clé du deuxième paramètre, $0$ sinon.
• void triFusion(linkedList* l, int (*inf)(void*, void*)), tri la liste l en modifiant le chaînage.
• Comparez son temps d'exécution à celui du tri par sélection. Déterminez sa complexité. Est-ce un algorithme de tri efficace ?