Écris une fonction sort(a) qui trie le tableau a sur place, ou pars d'un modèle. Elle s'exécute dans ton navigateur, à part de la page et avec une limite de 8 secondes, avec des tableaux de 8 à 1024 éléments déjà triés, à l'envers et aléatoires. Pas besoin de modifier ton code pour compter : chaque fois que tu compares deux éléments avec <, > ou en les soustrayant, cela compte comme une comparaison ; chaque a[i] est une lecture et chaque a[i] = …, une écriture.
Avec les grandes tailles, l'outil teste quelle courbe s'ajuste le mieux à tes comptages : n, n log n ou n², et avec quelle constante («≈ 0,5·n²»). C'est une mesure, pas une démonstration : un algorithme peut ressembler à du n log n à ces tailles sans en être un.
Un tri est stable si deux éléments ayant la même clé restent dans l'ordre où ils sont arrivés. La tool le vérifie avec un tableau plein de clés répétées qui mémorisent leur position d'origine.
Les comparaisons avec === (elles n'appellent pas valueOf) et ce que tu fais dans des tableaux auxiliaires, sauf quand tu réécris dans a. Comparer un élément avec un nombre isolé compte pour une demi-comparaison.
Écris ton tri (ou pars d'un modèle) et regarde combien il travaille vraiment : comparaisons, lectures et écritures, avec des tableaux de 8 à 1024 éléments.