Le choix d'un tri dépend de quelques propriétés : complexité temporelle, stabilité, utilisation mémoire in-place, et la nature des données. Aucun tri n'est gagnant partout.
Le choix d'un tri dépend de quelques propriétés : complexité temporelle, stabilité, utilisation mémoire in-place, et la nature des données. Aucun tri n'est gagnant partout.
| Algorithme | Temps moyen | Pire cas | Stable | In-place |
|---|---|---|---|---|
| Insertion | O(n²) | O(n²) | Oui | Oui |
| Fusion | O(n log n) | O(n log n) | Oui | Non |
| Rapide | O(n log n) | O(n²) | Non | Oui |
| Tas | O(n log n) | O(n log n) | Non | Oui |
# Most languages ship a tuned hybrid; prefer it in production
sorted(data, key=lambda x: x.priority) # stable Timsort in Python
Ne pas implémenter un tri soi-même à moins d'avoir une raison spécifique — les tris de bibliothèque (Timsort, introsort) sont des hybrides éprouvés.
Adapter le tri aux données et aux exigences évite à la fois du temps perdu et des bugs subtils (comme perdre la stabilité).
Comprendre les compromis explique pourquoi les bibliothèques standard ont choisi des hybrides comme Timsort et introsort.
Ce jugement comparatif — et non la mémorisation d'un algorithme — est ce que l'ingénierie réelle et les entretiens récompensent.