Sortowanie kubełkowe

Sortowanie kubełkowe jest nazywane również sortowaniem pozycyjnym.

Algorytm na początku ustala jakiego rzędu liczbami operuje ("który rząd") - ile cyfr ma największa z nich. Można to zrobić np. tak:
ile := log10(max{tab[1],...,tab[n]}) + 1.
Jeśli jednak wiadomo z góry, że liczby są np. nie większe niż 999, to od razu można przyjąć ile := 3 i pominąć wyżej podane obliczenia, co zaoszczędzi n-1 porównań i liczenie logarytmu.
Następnie algorytm dla każdego rzędu (najpierw cyfry jedności, potem dziesiątek, itd.) grupuje w kubełkach liczby z tablicy według cyfry na badanej pozycji, tzn. jeśli badana jest cyfra jedności, to w kubełku "3" znajdą się wszystkie liczby z tablicy, które mają cyfrę jedności równą 3, itd.
Kiedy algorytm przejrzy już wszystkie cyfry, to dane można uznać za posortowane.

Statystyka:

Zasadniczo algorytm ten wymaga ile*n "testów cyfry", "wpisań do kubełka" i "wyciągnięć z kubełka".

Uwagi:

Sortowanie kubełkowe jest bardzo szybkim algorytmem. Jeśli dodatkowo założy się np. istnienie nie 10, a 16 kubełków, to wyznaczanie poszczególnych cyfr zajmuje jedynie kilka taktów zegara procesora - są to przesunięcia bitowe oraz operacje logiczne (x AND 15). Poza tym kubełki implementuje się jako kolejki, gdzie właściwie można operować tylko na wskaźnikach, co również jest bardzo szybkie. Dodatkowo, ze względu na znajomość długości tablicy tab, można miejsce na wszystkie elementy wszystkich kolejek zarezerwować jako jeden blok w pamięci - wtedy po pierwsze nie traci się czasu na rezerwowanie n obszarów, a po drugie operacje na zwartym bloku są, ze względu na właściwości cache’a procesora, znacznie szybsze.
Oczywiście "nie ma róży bez kolców". Niestety algorytm ten nadaje się właściwie tylko do sortowania elementów, gdzie kluczami są liczby naturalne.
Mimo to, po pewnych przeróbkach, można go też użyć do sortowania krótkich tekstów.