A counting sort-nál mért volt gyorsabb bizonyos esetekben a pigeonhole sort?

A pigeonhole olyan elemek listájának rendezésére optimális, ahol az elemek száma (n) és a lehetséges kulcsértékek tartományának hossza (N) körülbelül azonos. Szükséges hozzá O(n + N) idő.

Hasonló a számláló rendezés is, de abban különbözik, hogy kétszer mozgatja az elemeket. Felépít egy kiegészítő tömböt, majd a tömb segítségével kiszámítja az egyes elemek végső helyét, és oda teszi azokat.