Sort elements by counting the frequency of their appearance of last digit
How It Works: Link to Video
- Worst Case Complexity: O(d*n+b) If we want to sort in ascending order and the array is in descending order then, the worst case occurs.
- Best Case Complexity: O(d*n+b) It occurs when the array is already sorted
- Average Case Complexity: O(d*n+b) It occurs when the elements of the array are in jumbled order (neither ascending nor descending).
d = no of digits in max element n = number of elements b = base of decimal number that is 10
- The space complexity of Radix Sort is O(n+b) where b is base that is usually 10
- Frequency Based
- Radix Based
- Stable
- Not Inplace
- Consumes very less memory than Counting Sort
- DC3 algorithm (Kärkkäinen-Sanders-Burkhardt) while making a suffix array.
- Places where there are numbers in large ranges.