Radix sort

O(d·(n + b))

Radix sort orders numbers by processing their digits, least-significant digit first. Each pass distributes the numbers into ten buckets by the current digit and then gathers them back in bucket order; because the distribution is stable, earlier-sorted digits stay ordered within each bucket. After the most-significant digit has been processed, the whole array is sorted. With d digits and base b it runs in O(d·(n + b)) — effectively linear when the numbers have a bounded number of digits. Each digit pass is itself a counting sort.

Array
Edit the input and press Play

How it works

  1. Start with the least-significant (ones) digit.
  2. Distribute every number into 10 buckets by that digit, keeping their order.
  3. Gather the buckets back together in order.
  4. Repeat for each higher digit — after the top digit, the array is sorted.

Pseudocode

1radixSort(a):                       # O(d·(n + b))2  for each digit position, LSD first:3    buckets ← 10 empty lists4    for v in a:5      d ← digit of v at this position6      buckets[d].append(v)            # stable distribute7    a ← concat(buckets[0..9])         # gather8  return a                            # sorted after the top digit