Radix Sort
Objectives
We would like to :- Investigate Radix Sort
Notes
-
Radix-Sort(A,d) Input: A, an array of elements identified by an integer key d, the number of digits in the key. Output: the array ordered by the key- for i ← 1 to d-1
- use any stable sort to sort on digit i
- This is O(d)*O(T(sort))
- But if we use counting sort, it is O(d*n)
- No extra space required for this algorithm. (But remember, counting sort is potentially bad)
- If you would like, see radix.cpp.