# What Is Radix Sorting in Data Structure?

//

Larry Thompson

Radix Sorting is a non-comparative sorting algorithm that works on integer keys by grouping digits. It belongs to the category of linear time sorting algorithms, along with counting sort and bucket sort. Unlike other comparison-based sorting algorithms like quicksort and mergesort, radix sort does not rely on comparisons between elements to determine their order.

## How does Radix Sorting work?

The basic idea behind radix sort is to sort the elements digit by digit, from the least significant digit (LSD) to the most significant digit (MSD). The algorithm makes multiple passes through the input data, each time distributing the elements into different buckets based on the value of the current digit being considered.

Let’s understand this with an example. Suppose we have an array of integers [170, 45, 75, 90, 802, 24, 2, 66].

In the first pass of radix sort, we consider the least significant digit (unit’s place) of each number and distribute them into different buckets based on their values. After this pass, our array would look like this: [802, 2, 24, 45, 75, 66, 170, 90].

In the second pass of radix sort, we consider the tens place of each number and distribute them into different buckets again. After this pass, our array would look like this: [802 ,2 ,24 ,45 ,66 ,170 ,75 ,90]. We repeat this process for as many digits as there are in the largest number in the array.

• Linear Time Complexity: Radix sort 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. This makes it faster than many comparison-based sorting algorithms in certain cases.
• Stable Sorting Algorithm: Radix sort is a stable sorting algorithm, meaning that it maintains the relative order of elements with equal keys. This is particularly useful when sorting objects or records with multiple fields.