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.


Leave a Reply