# What Is Radix Sort in Data Structure and Algorithm?

//

Heather Bennett

Radix sort is a sorting algorithm that operates on integers, treating them as strings of digits. It is a non-comparative sorting algorithm that sorts the elements by processing each digit at a time, from the least significant digit to the most significant digit. This algorithm is known for its efficiency when dealing with large datasets and has a time complexity of O(nk), where n is the number of elements and k is the number of digits in the largest element.

## How does Radix Sort work?

The radix sort algorithm works by distributing elements into buckets based on their digits. It repeatedly performs this distribution process for each digit, starting from the least significant digit to the most significant digit.

Let’s understand this with an example:

Consider an array of integers: [170, 45, 75, 90, 802, 24, 2, 66].

First Pass (Sorting by Least Significant Digit):

We start by considering the least significant digit (rightmost) of each element. In this case, it would be the ones’ place.

• 170 – Bucket 0
• 90 – Bucket 0
• 802 – Bucket 2
• 24 – Bucket 4
• 45 – Bucket 5
• 75 – Bucket 5
• 2 – Bucket 2
• 66 – Bucket 6

The elements are then collected from each bucket in order and placed back into the original array. After this pass, our array becomes: [170, 90, 802, 2, 24, 45, 75, 66].

Second Pass (Sorting by the Next Significant Digit):

We repeat the process, but this time considering the tens’ place digit.

• 170 – Bucket 7
• 90 – Bucket 0
• 802 – Bucket 0
• 2 – Bucket 0
• 24 – Bucket 2
• 45 – Bucket 4
• 75 – Bucket 7
• 66 – Bucket 6

The array becomes: [170, 90, 802, 2, 24, 45, 75, 66]. Notice that elements with the same tens’ place digit are sorted based on their previous sorting order.

Third Pass (Sorting by the Most Significant Digit):

We continue the process for the hundreds’ place digit:

• 170 – Bucket 1
• 90 – Bucket 0
• 802 – Bucket 8
• 2 – Bucket 0
• 24 – Bucket 2
The final sorted array is: [170,90,802,2,24,45‌​.75.66]

• Radix sort is an efficient algorithm for sorting large datasets.
• It is a stable sorting algorithm, preserving the order of elements with equal keys.
• Radix sort can be used to sort numbers in any base system, not just decimal (base-10).