Tri fusion
Coupe la liste en deux, trie chaque moitié, puis fusionne les deux moitiés triées en une seule liste triée.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(n)
- oui
- non
Meilleur cas : comment le temps grandit avec la taille n de la liste quand l'entrée est la plus facile pour cet algorithme.
Cas moyen : le temps habituel selon n. En n², deux fois plus de valeurs prennent quatre fois plus de temps ; n log n croît bien moins vite.
Pire cas : la croissance sur l'entrée la plus difficile. Utile quand la vitesse ne doit jamais chuter.
Espace : la mémoire supplémentaire nécessaire en plus de la liste. 1 veut dire quelques variables, n une copie de la liste.
Stable : deux valeurs égales gardent leur ordre d'origine. Important quand on trie des fiches selon un seul champ.
En place : trie à l'intérieur de la liste elle-même, sans deuxième liste.
- comparaison
- déplacement
- à sa place finale
Essayez : Choisissez peu de valeurs uniques. Entre deux valeurs égales, on prend d'abord celle de la moitié gauche, donc leur ordre est conservé.
Comment ça marche
On coupe la liste encore et encore, jusqu'à obtenir des morceaux d'une seule valeur, déjà triés. Puis on les fusionne deux par deux : on compare les premières valeurs des deux morceaux et on prend la plus petite, encore et encore. La ligne surélevée de l'animation est l'espace en plus utilisé pendant la fusion.
Quand le choisir
Quand il faut une vitesse qui reste bonne même dans le pire cas, et que les valeurs égales doivent garder leur ordre. Python et Java utilisent tous deux une variante du tri fusion. Son défaut est la mémoire en plus dont il a besoin.