Radix Sort: The radix sort is a non-comparative integer sorting algorithm that sorts the elements by grouping the individual digits of the same location. It shares the same significant position and value. Positional notation is required in this sorting. An excellent example of the radix sort is a dictionary because, in the dictionary, all the alphabets are arranged in alphabetical order. Radix sort was developed by the Harold H. Seward in 1954.

Complexity table of radix sort

ComplexityBest caseAverage caseWorst case
TimeΩ(n + k)θ(nk)O(nk)
Space  O(n + k)

Algorithm of radix sort

Example 1: Suppose we have the following array, which we have to sort.

542254864650875781453211152968

Example 2: Suppose we have the following array, which we have to sort.

65374321010632576972119918

Radix sort program in C language:

Output:

Pin It on Pinterest

Share This