# Implementing Radix Sort in Python

This tutorial will show you how to implement Radix sort on a list in Python. Radix sort is a type of ‘counting-based‘ sorting algorithm, as opposed to ‘comparison-based’ sorting algorithms.

The main idea behind Radix sort is to perform element-by-element sorting. This is done from least significant to most significant element. For eg, in the number, 123, 3 is the least significant digit and 1 is the most significant digit.

Now that we know what Radix sort is, let’s get started.

```# Function for sorting element by element

def Sort(a, y):

length = len(a)

# op is a list with length same as input list with all zeroes
op = [0] * length

# Counter will keep track of number of occurrences
counter = [0] * 10

for i in range(length):
index = int((a[i] / y))
counter[(index) % 10 ] += 1

# Counter i will now contain actual index position
for i in range(1,10):
counter[i] += counter[i-1]

# Inserting into op list
i = length-1
while i>=0:
index = int((a[i] / y))
op[ counter[(index) % 10] - 1] = a[i]
counter[ (index)%10 ] -= 1
i -= 1

# List op has the sorted elements. Now copying op elements to original list
i = 0
for i in range(0,len(a)):
a[i] = op[i]

# To find number of digits in the maximum number in the list.
maximum = max(a)

# Each digit is sorted
x = 1
while (maximum / x > 0):
Sort(a,x)
x *= 10

# Main Function

if __name__=="__main__":
print("Enter a list of decimal numbers seperated by a space :- ")
ip = list(map(int,input().split()))
print("List of Unsorted Numbers :- ")
for i in range(len(ip)):
print(ip[i])

print("\nList of Sorted Numbers :- ")
for i in range(len(ip)):
print(ip[i])```

First of all, when the main function executes, the user will input a list of numbers. The main function then calls the ‘Radix’ function to begin the process of radix sort.

In the Radix function, first, we find the maximum element in the list. This is done to find the maximum number of digits in a single number. Then, we begin sorting starting from the least significant digit using the Sort function.

In the Sort function, first, we create 2 lists. One, to store the output, and the other to serve as a counter. In the counter list, we are storing the number of digits of each element of the original input list. Then, we begin actually sorting the elements and begin inserting them into the final list.

Once we are done, we copy the contents of the op list into the original list. Now, the original list is sorted in increasing order.

### OUTPUT

```Enter a list of decimal numbers seperated by a space :-

7 2 1 9 10 11 4
List of Unsorted Numbers :-
7
2
1
9
10
11
4

List of Sorted Numbers :-
1
2
4
7
9
10
11```

If we have `log(n)` bits for every digit, Radix Sort performs slightly better than Quick Sort. So, for some cases, we can use Radix Sort instead of Quick Sort for a performance boost. However, Quick Sort uses hardware resources more efficiently and hence, is a better option for low-powered systems.

Time Complexity of Radix Sort : `(O(n+b) * log(base b)k)`

`b` is the base that represents the number (In case of decimals, it is 10)

`k` is the number of digits of the largest number in the list.