Time and Space Complexity

Time Complexity:

• O(d * (n + k))
  • where n is the number of elements, k is the base (10), and d is the number of digits in the largest value. Each of the d passes does O(n + k) work.
• When d is small and fixed, this behaves like O(n), faster than the O(n log n) of comparison sorts.

Space Complexity:

• O(n + k)
  • Each pass builds an output array of size n and a count array of size k.

Summary:

• Radix Sort is a stable, non-comparison sort that can beat O(n log n) for integer keys with a bounded number of digits.
• It needs keys that split into digits and some extra memory, and this version assumes non-negative integers.