Un algorithme de tri mal choisi peut multiplier le temps de calcul par mille

Deux façons de trier

Le tri par sélection cherche le plus petit élément, le place en tête, puis recommence sur le reste. Simple à écrire, il effectue de l'ordre de n² comparaisons.

Le tri fusion coupe le tableau en deux, trie chaque moitié récursivement, puis fusionne les deux moitiés triées. Il effectue de l'ordre de n log n comparaisons.

Sur 1 000 éléments : environ un million d'opérations contre dix mille, soit un facteur 100. Sur 1 000 000 d'éléments : mille milliards contre vingt millions, un facteur de plusieurs dizaines de milliers.

La leçon dépasse le tri : sur de petites données, tout fonctionne, et le choix de l'algorithme semble indifférent. C'est à grande échelle que la complexité décide entre un programme instantané et un programme inutilisable.