Résumé du chapitre 12

  Trions

• Le premier repose sur l'idée d'insertion d'un élément dans une liste triée : c'est le tri par insertion.
• Le second repose sur le principe ``diviser pour régner'' qui consiste à découper la liste en deux sous-listes, puis à trier ces deux sous-listes, et enfin à fusionner les deux listes obtenues  : c'est le tri par fusion.

Ces deux algorithmes ont des performances différentes en ce qui concerne le nombre de comparaisons effectuées (cf tableau ??).

  
Table: Performances des tris par insertion et par fusion

Pour étudier ces tris, nous avons dû distinguer le meilleur et le pire des cas.