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 on ż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 .

Implementacja w pseudojęzyku programowania

• tab[] – tablica ciagów (cyfr, liter itp.) gdzie pozycja 1 oznacza najbardziej znaczącą pozycje ciągu
• d – długość ciągów

procedure RadixSort(tab[],d)begin    for i:=d downto 1 do       posortuj stabilnie ciągi według i-tej pozycji;end;

Dowód poprawności algorytmu sortowania pozycyjnego

Załóżmy, że przed i-tym przebiegiem pętli for, wszystkie ciągi są posortowane według (i-1)tej cyfry/litery. Po kolejnej iteracji ciągi będą posortowane według i-tej. Jeżeli dla dwóch, lub więcej ciągów, ich i-ta cyfra/litera jest taka sama, stabilność sortowania zapewni nam zachowanie dobrego porządku. Po ostatnim przebiegu pętli for ciągi będą uporządkowane według najbardziej znaczących cyfr, oraz kolejnych w przypadku identyczności na ostatnich pozycjach.

Powyższy algorytm zakłada, że ciągi są tej samej długości. W przypadku gdy tak nie jest, możemy uzupełnić ciągi do tej samej długości zerami z lewej strony (dla liczb) lub zerowymi znakami z prawej (dla napisów). Jeżeli ciągów długich jest niewiele, metoda ta jest nieefektywna, jednak istnieją modyfikacje oryginalnego algorytmu działające ściśle w czasie liniowym względem rozmiaru danych.

Przykład działania algorytmu sortowania pozycyjnego

^ oznacza aktualną pozycję.523     472     523     266266     523     349     349783 --> 783 --> 266 --> 472472     266     472     523349     349     783     783   ^      ^      ^      ^