Résumé : Même si trier une permutation aléatoire requiert n log(n) comparaisons en moyenne, il existe de nombreux cas d'usage où les tableaux que l'on souhaite trier ne sont pas des permutations aléatoires : soit ils contiennent de longues plages contiguës déjà triées, soit ils contiennent peu de valeurs distinctes. L'algorithme TimSort, utilisé en Java pour trier des tableaux d'objets composites, a été conçu spécifiquement pour être plus efficace sur de tels tableaux pré-triés. Nous découvrirons comment cet algorithme et ses variantes fonctionnent et pourquoi ils sont efficaces.

Dernière modification : Friday 13 February 2026

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr