Next: Algorithmes Up: Tri par insertion Previous: Implémentation pour des vecteurs
L'implémentation pour les vecteurs est difficile à adapter pour les listes, car elle parcourt les données dans les deux sens, ce qui nécessiterait une liste doublement chaînée.
Une façon de résoudre ce problème est de maintenir deux listes, une correspondant à la partié déjà triée et l'autre contenant les éléments à insérer.
Il est souhaitable de réutiliser les cellules de la liste d'origine, afin d'éviter des allocations potentiellement coûteuses et des invocations supplémentaires du ramasse-miettes. Ceci veut dire que la liste d'origine sera complètement perturbée. Il est conseillé de ne pas utiliser la liste d'origine après l'invocation de cette implémentation (c'est la règle habituelle concernant les fonctions destructives Common Lisp).