Reference no: EM132363193

RADIX SORT ALGORITHM

The radix sorting algorithm is an integer sorting algorithm, that sorts by grouping numbers by their individual digits or radix which shares the same significant position. It uses each digit or radix as a key, and implements counting sort or bucket sort under the hood in order to do the work of sorting.

Comparison based sorting algorithms such as Merge Sort, Heap Sort, Quick-Sort time complexity is O(nlogn), Counting sort is a linear time sorting algorithm with time complexity O(n). We can't use counting sort for larger, multi-digit numbers because counting sort will take O(n2) which is worse than comparison based sorting algorithms.

Radix sort is a good choice for sorting larger, multi-digit sequences of fixed-length integer keys. it has lower computational complexity, and thus it is faster than comparison-based sorting algorithms.

Radix sort was the oldest algorithm ever invented. In the late 1800s an American inventor Herman Hollerith developed Radix sort algorithm to work on tabulating machine which used for processing data. This algorithm originally used for sorting punch cards and dictionaries. In a dictionary sorting of the words done from Most significant character to least significant character. Harold H. Seward invented a computer algorithm for radix sort in 1954 at MIT which developed as an alternative to comparison algorithms for large applications which needed speed.

There are two types of radix sorting:

Most significant digit (MSD) radix sort starts sorting from the beginning.

Least significant digit (LSD) radix sort starts sorting from the end.