25. Comparaison des Tris N log N (Merge vs. Quick)
| Caractéristique | Merge Sort | Quick Sort |
|---|---|---|
| Complexité Temporelle (Pire Cas) | O(N log N) | O(N²) |
| Complexité Temporelle (Moyen Cas) | O(N log N) | O(N log N) |
| Complexité Spatiale | O(N) (Pas en place) | O(log N) ou O(N) (En place, utilise la pile de récursivité) |
| Stabilité | Stable | Unstable |
| Utilisation Pratique | Idéal pour les linked lists, le tri externe, les exigences stables. | Algorithme de tri interne le plus rapide à usage général. |
Point Clé : Bien que le Quick Sort ait un pire cas théorique (O(N²)), sa performance moyenne est supérieure grâce à l'efficacité du cache et à une surcharge (overhead) plus faible. Si la stabilité ou un temps garanti dans le pire des cas est critique, le Merge Sort est le choix le plus sûr.