Introduction: The radix sort is a different type of sorting algorithm than others and is used by most people to sort a large list of names alphabetically. 'Radix' word can be defined as 'base' in the section of number conversion(like as decimal to binary or binary to octal decimal). Radix is different in the different representations of sorting. The list is given below,
Radix = 2 = for the bits
Radix = 10 = for the decimal digits
Radix = 26 = for the letters
Fig. 01: The radix
Radix Sort Time Complexity
Assume that an array data list 'a' of n items or n-length is given. The data array has (a1, a2, a3, ....., an) elements. Again assume that each item of the array 'a' can be represented by the 'p'. The 'p' is the passes needed to change the index number of the array elements.
Fig. 02: The data array 'a'
The radix sort depends on the three parameters. Parameters are,
r = r denote the radix or base of a number
p = p denote the passes needed for sorting elements
n = n denote the items in the array
The radix sort process will be required p passes for the number of numerals. Each of the passes will compare with n elements in the data array. Then, the number of comparisons for the n-length array is bounded by the following,
Radix(n) = r * p * n
Generally, the radix 'r' is independent of the n numbers but the 'p' passes depending on the n numbers. For the worst case, pass = numbers, then the time complexity can be written below,
worst case Radix(n) = O (1) * O(n) * O(n)
=O (n2)
For the best case, pass = logr n, then time complexity of radix sort will be,
Best case Radix(n) = O(1) * O(logr n) * O(n)
=O (n logr n)
In other words, the radix sort performs better when the number of n digits with p passes of the data array 'a' is small.
The drawback of the radix sort in the space complexity is that it needs r*n memory locations. But this drawback can be minimized using the linked list algorithm. However, the reality is, this sorting algorithm still needs two times of n-length memory location.
The space complexity of the radix sort is will be the same as the time complexity and that is O (n2)
Read Similar Post
3. Insertion Sort Time Complexity
4. Runtime Reduction of a Linear Search
5. Selection Sort Time Complexity