SortingSorting

Radix Sort (LSD)

Sort integers digit by digit from least significant to most, using a stable counting sort per digit.

Learn Radix Sort →
170
0
45
1
75
2
90
3
802
4
24
5
2
6
66
7
1/32The largest value 802 has 3 digit(s), so 3 pass(es) are needed. LSD radix sort sorts by ones, then tens, then hundreds, each time with a stable bucket distribution.
Element being bucketedDigit bucket receiving itSorted by digits so far
PseudocodeLearn Radix Sort →
1exp = 1
2while max(a) // exp > 0:
3  buckets = [[] for d in 0..9]
4  for x in a: buckets[(x // exp) % 10].append(x)   # stable
5  a = concat(buckets[0..9])
6  exp = exp * 10
Variables
exp1
digits3
Complexity
best O(d·(n + b))
avg O(d·(n + b))
worst O(d·(n + b))
space O(n + b)
Speed