Radix Sort

non-comparisonstableinteger-sort

Press play to start

1function radixSort(arr: number[]): number[] {
const max = Math.max(...arr)
for (let exp = 1; Math.floor(max/exp) > 0; exp *= 10) {
  const buckets: number[][] = Array.from({length:10},()=>[])
  for (const v of arr) buckets[Math.floor(v/exp)%10].push(v)
  arr = ([] as number[]).concat(...buckets)
}
return arr
9}

Step 1/0

Custom array:

Complexity

Best:O(d·n)
Average:O(d·n)
Worst:O(d·n)
Space:O(n+k)

Description

Sorts numbers digit by digit from least significant to most significant, using a stable sort (like counting sort) for each digit pass.

When to use

O(d·n) where d is number of digits. Efficient for integers and strings with bounded length. Used in suffix array construction.