Radix sort is a noncomparative sorting algorithm that orders keys by processing one digit position at a time in a fixed number base. A least-significant-digit radix sort processes positions from right to left and requires the sort at each position to be stable. A most-significant-digit radix sort processes positions from left to right and recursively sorts the resulting buckets.
For 
keys having 
digits drawn from an alphabet of size 
, a bucket implementation takes 
time and 
auxiliary space.
