Introduction of Radix Sort

Radix Sort is the answer when elements are in the range from 1 to n^2. The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit. Radix sort uses counting sort as a subroutine to sort.

Radix Sort:

Radix Sort basically consists of the following steps:

Take the Least Significant Digit of each element
Sort the list of elements based on the digit, but keep the order of elements with the same digit i.e. sorting stably.
Repeat the sort with each more significant digit.

Radix sort can be implemented in many ways like counting sort and bucket sort. Here, we’ll be using bucket sort technique. Bucket sort is mainly useful when input is uniformly distributed over a range.

Time Complexity:

T(n) = O(nd)  ≈ O(n) , if d is small
Here, n is input size
d is number of digits in input integers.

Implementation of Radix Sort :

Following is a simple implementation of radix sort in Python.
For easier understanding, the value of radix, r is 10.
It is recommended to go through Bucket Sort for understanding why how bucket sorting works.

# Python program for implementation of Radix Sort using bucket sort technique
def radixSort(a):
    # radix
    r = 10
    maxlength = False
    temp, place = -1, 1
    while not maxlength:
        maxlength = True
        # create buckets size 10 as integers are decimal numbers 
        # so they can hold numbers from 0-9 only, that's why size of 10
        buckets = [list() for _ in range(r)]
        for i in a:
            temp = int(i/place)
            # store elements in buckets 
            # using least significant digit as bucket index
            buckets[temp % r].append(i)
            if maxlength and temp > 0:
                maxlength = False
        d = 0
        for b in range(r):
            buck = buckets[b]
            # store back elements in array A
            # in the same order they're stored in buckets
            for i in buck:
                a[d] = i
                d += 1
        place *= r


# create array
a = [18, 4, 823, 61, 234]
#Function call
radixSort(a)
#function to print the sorted array
for i in range(len(a)):
    print(a[i])

Output:

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.