Sortowanie pozycyjne (ang. radix sort) to algorytm sortowania porządkujący stabilnie ciągi wartości (liczb, słów) względem konkretnych cyfr, znaków itp, kolejno od najmniej znaczących do najbardziej znaczących pozycji. Złożoność obliczeniowa jest równa O(d(n + k)), gdzie k to liczba różnych cyfr, a d liczba cyfr w kluczach. Wymaga O(n + k) dodatkowej pamięci.

Przewagą sortowania pozycyjnego nad innymi metodami jest fakt, iż nie wykonuje ono żadnych operacji porównania na danych wejściowych. Załóżmy że mamy dużą liczbę bardzo długich liczb, bardzo do siebie podobnych – w tym sensie, że większość z nich ma takie same cyfry na początkowych pozycjach. Nie jest łatwo powiedzieć która jest większa, gdyż za każdym razem musimy porównać dużo cyfr zanim trafimy na różnicę. Czas porównania takich liczb jest zatem proporcjonalny do ich długości. Gdybyśmy do posortowania tych liczb zastosowali algorytm porównujący liczby, np. sortowanie szybkie, otrzymalibyśmy dla niego złożoność O(dnlogn) gdzie d to liczba cyfr w liczbach.

Algorytmy pozycyjne sprawdzają się także w roli algorytmów sortujących listy.

Algorytm

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.

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. Jeś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 log n).