Tri fusion

1. 1

   Indice

   Calculer la longueur de la liste puis parcourir ses indices pour répartir les éléments dans deux nouvelles listes.
   Écrire une fonction decouper_en_2(t) qui renvoie un tuple contenant deux listes correspondant respectivement à la première et à la seconde moitié de la liste t. Par exemple decouper_en_2([1, 2, 3, 4]) renvoie ([1, 2], [3, 4]).
2. 2

   Indice

   Déterminer l'indice médian de la séquence puis appliquer la syntaxe de tranchage (tab[start:stop]) pour extraire les deux moitiés.
   Écrire une fonction slice_2(t) qui renvoie un tuple contenant les deux moitiés de la liste t en utilisant les tranches. Par exemple slice_2([1, 2, 3, 4]) renvoie ([1, 2], [3, 4]).
3. 3

   Indice

   Comparer les premiers éléments des deux listes triées puis appeler la fonction de fusion sur les listes restantes. Penser aux conditions d'arrêt de l'algorithme.
   Écrire une fonction récursive fusion(t1, t2) qui renvoie une liste triée contenant tous les éléments des listes triées t1 et t2. Par exemple fusion([1, 3], [2, 4]) renvoie [1, 2, 3, 4].
4. 4

   Indice

   Utiliser deux indices de parcours i1 et i2 pour chaque liste t1 et t2. Aancer systématiquement celui qui pointe sur la valeur la plus petite.
   Écrire une fonction impérative fusionner(t1, t2) qui calcule une liste triée contenant tous les éléments des listes triées t1 et t2 sans utiliser de récursivité. Par exemple fusionner([1, 3], [2, 4]) renvoie [1, 2, 3, 4].
5. 5

   Indice

   Diviser récursivement la liste en sous-listes jusqu'à obtenir des éléments isolés puis les recombiner en ordre croissant. Une liste à 0 ou 1 élément est déjà triée !
   Écrire une fonction récursive tri_fusion(t) qui renvoie une liste triée contenant les mêmes éléments que la liste t en utilisant l'algorithme du tri fusion. Par exemple tri_fusion([3, 1, 4, 2]) renvoie [1, 2, 3, 4].