Bucket Sort - Pseudocode

Pseudocode

function bucketSort(array, n) is buckets ← new array of n empty lists for i = 0 to (length(array)-1) do insert array into buckets, k)] for i = 0 to n - 1 do nextSort(buckets) return the concatenation of buckets, ...., buckets

Here array is the array to be sorted and n is the number of buckets to use. The function msbits(x,k) returns the k most significant bits of x (floor(x/2^(size(x)-k))); different functions can be used to translate the range of elements in array to n buckets, such as translating the letters A–Z to 0–25 or returning the first character (0–255) for sorting strings. The function nextSort is a sorting function; using bucketSort itself as nextSort produces a relative of radix sort; in particular, the case n = 2 corresponds to quicksort (although potentially with poor pivot choices).