### Introduction to Radix Sort

**The radix** (or **base**) is *the number of digits* used to represent numbers in a *positional numeral system*. For *the binary system*, the radix is *2* (it uses only two digits - 0 and 1). For *the decimal system*, the radix is *10* (it uses ten digits to represent all numbers - from 0 to 9).

A positional numeral system is, in simple terms, a number writing system, where the weight (or the value) of a digit is determined by its position. For example, in the number

`123`

,`1`

has more value than`3`

because it's in position that denotes hundreds, and the`2`

is in the tens.

**Radix Sort** can be used to lexicographically sort many types of data - integers, words, emails, but is mainly used to sort collections of *integers* and *strings* (that are mapped to appropriate integer keys).

It's a non-comparative sorting algorithm, meaning that it doesn't sort a collection by comparing its individual elements, but rather uses the inherent nature of the data its sorting to sort faster - it sorts data based on their *radix*.

Comparative sorting algorithms have the best case time complexity of

O(nlogn), which is comparatively worse tolinear execution time(O(n+k)) of non-comparative algorithms.

For example, let `n`

be the number of elements to be sorted, and `k`

is the range of allowed element values.

*Counting Sort* (a popular non-comparative algorithm) has the complexity of `O(n+k)`

when the `k`

is in the range from `1..n`

. But, if elements range from `1..n²`

, then the complexity rises to `O(n²)`

, which is worse than any comparative sorting algorithm.

Counting Sort has the *potential* to be significantly faster than other popular comparative algorithms, though, only if a certain condition was fulfilled.

The idea of the Radix Sort is to **upgrade Counting Sort so that it maintains the linear time complexity** even if the range of elements' values drastically exceeds the number of elements.

In fact, *Radix Sort* inherently uses *Counting Sort* as the main subroutine, with a few tweaks to overcome the issues that arise with an incrased range of elements' values.

- Counting Sort Algorithm
- Why Use Counting Sort?
- How does Counting Sort work?
- Implementing Counting Sort
- Counting Sort Complexity
- Radix Sort Algorithm
- Implementing Radix Sort
- Radix Sort Complexity

### Counting Sort Algorithm

In order to get a grasp of Radix Sort, we'll have to delve into Counting Sort first, implement it and observe the downfall with an increased number of element values.

#### Why Use Counting Sort in the Radix Sort?

Counting sort is a *stable*, *non-comparative* sorting algorithm, and it is mainly used to sort integer arrays. All of these characteristics are important for its use in Radix Sort. You *can* use other algorithms as the subroutine, as long as they have these characteristics, though, Counting Sort is the most natural matchup.

Radix Sort needs to maintain a relative order of elements with the same key values in the input array while sorting the same place value digits, therefore, our main subroutine by definition needs to be some sort of **stable sorting algorithm:**

**Non-comparative sorting algorithms** generally have linear complexity, so they will have less impact on the complexity of the Radix Sort.

#### How Does the Counting Sort Work?

Let's take a look at an unsorted integer array, which we'll sort using Counting Sort:

```
I = [2, 2, 0, 6, 1, 9, 9, 7]
```

Counting Sort works by

counting the number of elements, that fit adistinct key value, and then calculates the positions of each key.

First of all, we'll find the maximum element in the input array - `max = 9`

.

Then, we'll create an auxiliary array with `max+1`

elements. This is the *count array* (`C`

), which will be used to store the number of occurrences of each element in the *input array*.

Initially, all counts are initialized to 0:

```
C = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # Count array
#indices: 0 1 2 3 4 5 6 7 8 9
```

**Now, we need to go through the following steps:**

**1.** Traverse the *input array* and increase the corresponding count for every element by `1`

For example, if we come across an element with the value of `2`

in the *input array* (`I`

), we add 1 to the element with the index `2`

in the *count array*:

```
I = [2, 2, 0, 6, 1, 9, 9, 7] # The first element is 2
^
C = [0, 0, 1, 0, 0, 0, 0, 0, 0, 0] # We increase count of 2nd element by 1
#indices: 0 1 2 3 4 5 6 7 8 9
```

After this step, the *count array* will store the number of occurrences of each element in the *input array*:

```
C = [1, 1, 2, 0, 0, 0, 1, 1, 0, 2]
#indices: 0 1 2 3 4 5 6 7 8 9
# Element 0 has 1 occurrence
# Element 1 has 1 occurrence
# Element 2 has 2 occurrences
# Element 3 has no occurrences...
```

**2.** For each element in the *count array*, sum up its value with the value of all its previous elements, and then store that value as the value of the current element:

```
C = [1, 2, 4, 4, 4, 4, 5, 6, 6, 8]
#indices: 0 1 2 3 4 5 6 7 8 9
# Element 0 = 1
# Element 1 = 1 + 1
# Element 2 = 1 + 1 + 2
# Element 3 = 1 + 1 + 2 + 0
#...
```

This way, we are storing the cumulative sum of the elements of the *count array*, on each step.

**3.** Calculate element position based on the *count array* values

To store this sorted sequence, we'll need to create a new array. Let's call it the *output array* (`O`

), and initialize it with `k`

zeros, where `k`

is the number of elements in the *input array*:

```
O = [0, 0, 0, 0, 0, 0, 0, 0] // Initialized output array
#indices: 0 1 2 3 4 5 6 7
```

**For each element I[i] (starting from the end) in the input array:**

- Find the index in the
*count array*that is equal to the value of the current element`I[i]`

- That's the element
`C[j]`

where`j=I[i]`

- That's the element
- Subtract
`1`

from the value of the`C[i]`

- Now we have
`newValue = C[i]-1`

- Now we have
- Store the
`I[i]`

to the`O[newValue]`

- Update the
`C[i]`

with the`newValue`

In the end, the *output array* contains the sorted elements of the input array!

#### Implementing Counting Sort in Python

Now, with all that out of the way - let's go ahead an implement Counting Sort in Python:

```
def countingSort(inputArray):
# Find the maximum element in the inputArray
maxEl = max(inputArray)
countArrayLength = maxEl+1
# Initialize the countArray with (max+1) zeros
countArray = [0] * countArrayLength
# Step 1 -> Traverse the inputArray and increase
# the corresponding count for every element by 1
for el in inputArray:
countArray[el] += 1
# Step 2 -> For each element in the countArray,
# sum up its value with the value of the previous
# element, and then store that value
# as the value of the current element
for i in range(1, countArrayLength):
countArray[i] += countArray[i-1]
# Step 3 -> Calculate element position
# based on the countArray values
outputArray = [0] * len(inputArray)
i = len(inputArray) - 1
while i >= 0:
currentEl = inputArray[i]
countArray[currentEl] -= 1
newPosition = countArray[currentEl]
outputArray[newPosition] = currentEl
i -= 1
return outputArray
inputArray = [2,2,0,6,1,9,9,7]
print("Input array = ", inputArray)
sortedArray = countingSort(inputArray)
print("Counting sort result = ", sortedArray)
```

Running the code above will yield us the following output:

```
Input array = [2, 2, 0, 6, 1, 9, 9, 7]
Counting sort result = [0, 1, 2, 2, 6, 7, 9, 9]
```

#### Counting Sort Complexity

The time complexity of the counting sort is `O(n+k)`

, where `n`

is the number of elements in the *input array*, and `k`

is the value of the `max`

element in the array.

The problem occurs when the value of the largest element drastically exceeds the number of elements in the array. As the `k`

approaches `n²`

, the time complexity gets closer to `O(n²)`

, which is a horrible time complexity for a sorting algorithm.

This is where Radix Sort kicks in.

### Radix Sort Algorithm

Instead of counting the elements by their distinct key value - Radix Sort groups digits by their *positional value* and performing Counting Sort in each group. The starting position can vary - *LSD (Least Significant Digits)* or *MSD (Most Significant Digits)* are two common ones, and accordingly, these variations of Radix Sort are called LSD Radix Sort and MSD Radix Sort.

Let `I = [2, 20, 61, 997, 1, 619]`

be the input array that we want to sort:

We'll focus on *LSD Radix Sort*.

#### Radix Sort Algorithm

The steps taken by Radix Sort are fairly straighforward:

- Find the maximum element in the input array -
`max = 997`

- Find the number of digits in the
`max`

element -`D = 3`

- Initialize the place value to the least significant place -
`placeVal = 1`

- For
`D`

times do:- Perform the counting sort by the current place value
- Move to the next place value by multiplying
`placeVal`

by 10

### Implementing Radix Sort in Python

And finally, with that out of the way, let's implement Radix Sort in Python:

```
def countingSortForRadix(inputArray, placeValue):
# We can assume that the number of digits used to represent
# all numbers on the placeValue position is not grater than 10
countArray = [0] * 10
inputSize = len(inputArray)
# placeElement is the value of the current place value
# of the current element, e.g. if the current element is
# 123, and the place value is 10, the placeElement is
# equal to 2
for i in range(inputSize):
placeElement = (inputArray[i] // placeValue) % 10
countArray[placeElement] += 1
for i in range(1, 10):
countArray[i] += countArray[i-1]
# Reconstructing the output array
outputArray = [0] * inputSize
i = inputSize - 1
while i >= 0:
currentEl = inputArray[i]
placeElement = (inputArray[i] // placeValue) % 10
countArray[placeElement] -= 1
newPosition = countArray[placeElement]
outputArray[newPosition] = currentEl
i -= 1
return outputArray
def radixSort(inputArray):
# Step 1 -> Find the maximum element in the input array
maxEl = max(inputArray)
# Step 2 -> Find the number of digits in the `max` element
D = 1
while maxEl > 0:
maxEl /= 10
D += 1
# Step 3 -> Initialize the place value to the least significant place
placeVal = 1
# Step 4
outputArray = inputArray
while D > 0:
outputArray = countingSortForRadix(outputArray, placeVal)
placeVal *= 10
D -= 1
return outputArray
input = [2,20,61,997,1,619]
print(input)
sorted = radixSort(input)
print(sorted)
```

Running the code above will yield us the following output:

```
[2, 20, 61, 997, 1, 619]
[1, 2, 20, 61, 619, 997]
```

### Radix Sort Complexity

As we stated before, Radix Sort has **linear time complexity**. If we use *Counting Sort* as the main subroutine, the complexity of radix sort is `O(d(n+k))`

. That is because we are executing the counting sort `d`

times, and the complexity of the *Counting Sort* itself is `O(n+k)`

.

### Conclusion

Radix sort is a great sorting algorithm to use in some specific cases. Some benchmarks have even shown that radix sort can execute up to 3 times faster than other, more general-purpose sorting algorithms.

It shines when the input array has shorter keys, or the range of the element values is smaller. But has poor space complexity in other cases, when the range of element values is quite large and elements have too many digits in their representation.

That is the main reason why the radix sort is not as widely used as some other types of sorting algorithms, even if it has linear time complexity.