Radix Sort

In computer science, radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered. For this reason, radix sort has also been called bucket sort and digital sort. (Source: Wikipedia)

Advantages:

• Fast when the keys are short i.e. when the range of the array elements is less.
• Used in suffix array constuction algorithms like Manber's algorithm and DC3 algorithm.

Disadvantages:

• Since Radix Sort depends on digits or letters, Radix Sort is much less flexible than other sorts. Hence , for every different type of data it needs to be rewritten.
• The constant for Radix sort is greater compared to other sorting algorithms.
• It takes more space compared to Quicksort which is inplace sorting.

(Source: Hackerearth)

Pseudocode

radixSort(array)
  d <- maximum number of digits in the largest element
  create d buckets of size 0-9
  for i <- 0 to d
    sort the elements according to ith place digits using countingSort
countingSort(array, d)
  max <- find largest element among dth place elements
  initialize count array with all zeros
  for j <- 0 to size
    find the total count of each unique digit in dth place of elements and
    store the count at jth index in count array
  for i <- 1 to max
    find the cumulative sum and store it in count array itself
  for j <- size down to 1
    restore the elements to array
    decrease count of each element restored by 1

Complexity

References

• Geeksforgeeks
• Wikipedia
• YouTube
• Programiz
• Hackerearth