What is the time complexity of radix sort?

Best case O(d(n + b)). Average case O(d(n + b)). Worst case O(d(n + b)). Space complexity is O(n + b). d digits, b buckets. For 32-bit integers d is a constant.

Radix sort

medium

Least-significant digit first looks backwards but is the only order that works with a stable sub-sort: each pass refines the last without destroying it. Genuinely linear for fixed-width keys.

Best O(d(n + b))Average O(d(n + b))Worst O(d(n + b))Space O(n + b)StableNeeds extra memory

Loading the radix sort engine…

Where to go next

Counting sort

medium

Sorting with zero comparisons.

Bucket sort

medium

Scatter by value range, sort each bucket, concatenate.

Hash table with chaining

medium

Collisions share a bucket, and load factor is everything.