Complexités des tris
IntermédiaireQuel tri, quand, et à quel prix.
| Tri | Moyenne | Pire cas | Mémoire | Note |
|---|---|---|---|---|
| Fusion (merge sort) | O(n log n) | O(n log n) | O(n) | Stable, complexité garantie |
| Rapide (quicksort) | O(n log n) | O(n²) | O(log n) | Très rapide en pratique, pire cas si le pivot est mal choisi |
| Tas (heapsort) | O(n log n) | O(n log n) | O(1) | En place, non stable |
| Comptage | O(n + k) | O(n + k) | O(k) | k = amplitude des valeurs, entiers bornés uniquement |
sort() Python / Java | O(n log n) | O(n log n) | O(n) | Timsort : stable, adapté aux données partiellement triées |