Pozycją (ang. radix) nazywamy miejsce cyfry w zapisie liczby. Sortowanie pozycyjne polega na sortowaniu elementów wg kolejnych (licząc od końca) cyfr liczby. Algorytm sortujący musi być stabilny, tzn. nie może zmieniać kolejności elementów równych, w przeciwnym razie efekty poprzednich sortowań zostaną utracone.
Przykład:
Posortować algorytmem sortowania pozycyjnego zbiór liczb:
| { 547 398 247 153 121 792 421 } |
Liczby posortujemy wg kolejnych od końca cyfr:
| start | ??x | ?x? | x?? | koniec |
| 547 398 247 153 121 792 421 | 121 421 792 153 547 247 398 | 121 421 547 247 153 792 398 | 121 153 247 398 421 547 792 | 121 153 247 398 421 547 792 |
Po posortowaniu ostatniej cyfry liczby tworzą ciąg posortowany.
Sortowanie wg poszczególnych cyfr możemy przeprowadzić w czasie liniowym. Operację musimy wykonać tyle razy, z ilu cyfr zbudowane są liczby reprezentujące sortowane elementy.
eśli liczby są równomiernie rozłożone w reprezentowanym zbiorze, to n elementów może mieć do (logpn + 1) cyfr, gdzie p jest podstawą systemu zapisu liczb. Zatem czas sortowania będzie proporcjonalny do iloczynu n(logpn + 1). Klasa złożoności obliczeniowej jest równa O(n logn).