Radix Sort

If you are familiar with Counting sort and Bucket sort, you should know that these two sorting methods are special sorting methods that can break through the complexity O(nlog n) limit of the comparison sorting method. Radix sort is also a special integer sorting method, and its performance can also break through limits. The difference is that the first two only sort based on one key value, while Radix sort sorts based on multiple key values.

For example, if you want to sort a group of integers in the range 0 - 999, if you use Counting sort, you need to create an "array of 1000 elements" to count the number of occurrences of each integer; if you use Radix sort with 10 as the base, Then you only need to sort three times using single digits, tens digits, and hundreds digits as key values. Usually Radix sort's sorting subroutine will use Counting sort or Bucket sort, and the key value range based on 10 is only 0 - 9. This small range of integers is very suitable for Counting sort as a sorting subroutine, saving configuration The time and space of the count array of int arr[1000].

The basic features of Radix sort are as follows:

• Integer sorting method: Use integers as the key values ​​for sorting.

• Distributive sorting method: Sorting is done by analyzing key value distribution rather than pairwise comparison. Linear execution times can be achieved under certain circumstances.

Radix sort using LSD is a stable sorting method; through optimization, using MSD can also be a stable sorting method.

Source of image: https://www.geeksforgeeks.org/radix-sort/