Radix Sort

Reading Time: 2 minutes

Definition

The optimal algorithm for the numbers range from 1 to n2. Radix Sort algorithm favors of Counting Sort internally to sort the array. The given keys consists of the digits in each element in the array.
It starts from the Least Significant Digit which is the left digit, then goes to the Most Significant Digit which means to the right.

Each digit goes to a corresponding numbered buckets. After the buckets is filled with the elements in the array, the elements are sorted once again according to the bin position. Let’s us see an example illustration to better apprehend the logic, we will sort the numbers “551, 12, 346, 311”;

Visual Array Status of Sorting Phases by Radix Sort
Statuses of Buckets in each pass

Now we have more or less how the Radix Sort works out internally. There is one gap I’d like to point what happens to 12 which has two digits compared to the others that have three digits. Well in this situation such numbers are appended with leading 0s and they always sit on the bucket zero.
n numbers consisting of k digits

Complexity

Time Complexity

n: number of elements
k: the range of the keys for each number. We will also repeat the operation for this amount.
All of the Time Complexities of Radix Sort is always O(n*k)

Space Complexity

Space complexity of Radix Sort is O(n+k)

Code

You can checkout my GitHub repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Leave a Reply

Your email address will not be published. Required fields are marked *