Quick Facts
- Non-comparitive sorting algorithm.
- Running time is \(O(d*(n+b))\), where \(d\) is the number of \(digits\), and \(b\) is the \(base\).
- Runtime of \(O(n)\) when we sort an array of integers with range from \(1 — n^c\), where \(c\) is a constant, if the numbers are represented in base \(n\); or every digit takes \(log_2(n)\) bits.
- Uses Counting Sort or Bucket Sort as a subroutine. We use the subroutine to sort one digit at a time.
