De ce contează?
Profesorul strigă catalogul și vrea notele clasei în ordine. În loc să le rețină una câte una și apoi să le rearanjeze, trage pur și simplu liniuțe pe o foaie: una pentru fiecare elev cu nota 1, una pentru fiecare cu nota 2, și așa mai departe. La final citește foaia de sus în jos — „un 4, trei de 7, doi de 9" — și are instant șirul ordonat, fără să fi comparat vreodată două note între ele. Asta e sortarea prin numărare.
Intuiția
Dacă valorile pe care le sortezi sunt numere mici dintr-un interval cunoscut, nu ai nevoie de comparații. Numeri câte apariții are fiecare valoare, apoi parcurgi contoarele în ordine crescătoare și rescrii fiecare valoare de atâtea ori cât a apărut. Ordinea apare singură din ordinea naturală a indicilor.
Două idei într-una: numeri câte din fiecare valoare ai (un contor pe valoare), apoi reconstruiești șirul parcurgând contoarele de la mic la mare. Nicăieri nu compari două elemente între ele — ordinea iese gratuit din ordinea indicilor.