Il y a beaucoup de tris existants ('suffit d'aller jeter un oeil sur Wikipedia et dans quelques bouquins d'algorithmique). Mais mon préféré, c'est celui qui est mentionné dans une quote de QDB :
  • Choisir un générateur aléatoire qui s'inscrit dans la mécanique quantique
  • Permuter aléatoirement le tableau selon ce générateur
  • Si le tableau n'est pas trié à la fin du nombre minimal de permutations pour arriver au tableau trié, détruire l'univers
  • Donc il reste un ensemble d'univers dans lequel le tableau est trié (puisqu'on est là pour en parler), et le tri s'est fait en temps linéaire (puisqu'on associe un échange dans le tableau par événement aléatoire).
Ça fait quand même un gros gaspillage d'énergie pour trier en temps linéaire un tableau... Mais il est correct.