Tellesortering: tall i bokser

Hvorfor kan vi sortere ti tall raskere enn n log n når tallene er små? Tellesortering sammenligner ingen par i det hele tatt — den gir hver mulig verdi sin egen boks, slipper input ned i riktig boks i én runde, og tømmer så boksene fra venstre mot høyre rett ut i utlista. Ti tall mellom én og seks faller en etter en ned i seks bokser, så strømmer ut igjen i sortert orden. Kjøretiden lander på orden n pluss k — lineær når k er liten.