Les principaux tris
TriIdéeComplexitéSélectionplacer le minimum restantO(n²)Insertioninsérer chaque élément à sa place (rapide si presque trié)O(n²)Fusioncouper en deux, trier, fusionnerO(n log n)Rapide (quicksort)partitionner autour d'un pivotO(n log n) en moyenneComplexité
O(n²) : 1 000 éléments → ~1 000 000 d'opérations ; O(n log n) → ~10 000. D'où l'importance du choix de l'algorithme sur de gros volumes.
En pratique
sorted(notes, reverse=True)
personnes.sort(key=lambda p: p["age"])Python utilise Timsort (stable, très efficace). Voir aussi la recherche dichotomique, la récursivité.