RADIX SORT

WHAT IS
RADIX SORT?
Radix Sort
• Radix sort is a non-comparative sorting algorithm
that sorts integers by processing individual digits
• Radix sort can be performed in two ways: Most
Significant Digit and Least Significant Digit radix
sort
USES OF RADIX
SORT
Radix sort is useful for:
• Integer sorting: It sorts numbers by their digits from LSD to MSD.

• Fixed-length string sorting: It sorts strings by their characters’ ASCII or

Unicode values.

• Digital signal processing: It sorts data by their binary digits.

• Graphics processing: It sorts pixels by their color components.

• External sorting: It sorts large datasets by using external storage and

processing chunks of data.
 Radix Sort

A D VA N TA G E S D I S A D VA N TA G E S
• Linear Time Complexity for Fixed-Length Keys: • Not Suitable for Variable-Length Keys:
Radix sort has a linear time complexity for sorting integers or fixed-length strings. Its time Radix sort is less practical when dealing with variable-length keys. The algorithm's efficiency is
complexity is O(nk), where n is the number of elements to be sorted, and k is the length of closely tied to the length of the keys being sorted, and when the keys have varying lengths,
the keys. Counting Sort = O( n+k ) Radix Sort = O( d ( n+k ) ) other sorting algorithms like quicksort or mergesort may be more suitable.

• Stability: • Space Complexity:

Radix sort is a stable sorting algorithm. Stability means that equal elements maintain their Radix sort can have a high space complexity, especially when dealing with large integers. The
relative order in the sorted output. This property is important in applications where the need to create buckets for each digit or character can result in increased memory requirements,
original order of equivalent elements needs to be preserved. making it less memory-efficient than some in-place sorting algorithms.

• Limited Applicability to General Sorting:

• No Comparison Operation:
While radix sort excels in certain scenarios, it is not as universally applicable as some other
Unlike many sorting algorithms, radix sort does not rely on comparison operations between
sorting algorithms like quicksort or mergesort. Its efficiency depends on the specific
elements. Instead, it exploits the structure of the keys being sorted by processing individual
characteristics of the data being sorted.
digits.
• Not Always the Fastest:
• Adaptability to Parallel Processing:
Radix sort might not always be the fastest sorting algorithm, depending on the nature of the
Radix sort can be adapted for parallel processing, which can lead to improved performance
data and the available memory. Other algorithms, such as quicksort, may perform better in
on multi-core or parallel computing architectures. The independent processing of digits or
certain situations, especially when dealing with smaller datasets or data with a wide range of
groups of digits allows for parallelization.
key values.
• Applicability to Specific Data Types: • Not In-Place:
Radix sort is well-suited for sorting integers and fixed-length strings with the same length. Radix sort is typically not an in-place sorting algorithm. It often requires additional storage to
In scenarios where the data conforms to these criteria, radix sort can outperform other store the buckets during the sorting process. This can be a drawback in situations where
algorithms. memory usage is a critical concern.
LSD
LSD (Least Significant Digit)Start from the least significant
digit (rightmost) and move towards the most significant digit
(leftmost). For each pass, elements are sorted into buckets
according to the value of the current digit.
After processing all digits, the elements are sorted.
 LSD

A D VA N TA G E S D I S A D VA N TA G E S

• Simplicity of Implementation: • Inefficiency with Variable-Length Keys:

LSD radix sort is generally simpler to implement than MSD radix sort. The algorithm
processes digits from the least significant digit to the most significant digit, making it more LSD radix sort is less efficient when dealing with variable-length keys.
straightforward. It processes each position individually, and when keys have varying
• Stable Sorting:
lengths, there may be inefficiencies in handling shorter or longer keys.

LSD radix sort is inherently stable, meaning that equal elements maintain their relative order after
sorting. This stability can be crucial in applications where maintaining the original order of
equivalent elements is important. • Wasted Work on Leading Zeros:
• Efficient for Fixed-Length Keys: LSD radix sort spends time processing leading zeros, which can be a
LSD radix sort is efficient when sorting fixed-length keys, such as integers or strings waste of computational resources. This is especially relevant when
with consistent length. It takes advantage of the positional representation of numbers.
sorting integers with a wide range of values, leading to unnecessary
iterations through zero-padded positions.
• Adaptable to External Sorting:

LSD radix sort can be adapted for external sorting scenarios, where the data doesn't fit entirely
into memory. Processing data from the least significant digit to the most significant digit allows for
efficient handling of external storage.
MSD (Most Significant Digit)
• Start from the most significant digit
(leftmost) and move towards the
least significant digit
(rightmost). For each pass, elements
are sorted into buckets based on the
value of the current digit.
Recursively apply the same process
to each bucket until all digits have
been processed.
 MSD
A D VA N TA G E S D I S A D VA N TA G E S

• Efficiency with Variable-Length Keys: • Potential Lack of Stability:

MSD radix sort is more efficient when dealing with variable-length keys. It MSD radix sort, as traditionally implemented, may not be stable when sorting. Ensuring
stability might require additional steps, such as using stable sorting algorithms within
can handle keys of different lengths by dynamically adapting the number of
each bucket.
digits processed at each recursive step.
• Complexity of Implementation:
MSD radix sort, especially when stability needs to be maintained, can be more complex
• Early Termination for Short Keys: to implement than LSD radix sort. Careful handling is required to ensure correct sorting
and stability.
MSD radix sort can terminate early for keys that are shorter than the
maximum key length. This can result in improved performance when dealing • Less Natural for External Sorting:
with datasets containing keys of varying lengths. MSD radix sort is less naturally adapted to external sorting compared to LSD radix sort.
External sorting involves efficiently handling data that doesn't fit entirely into memory,
and the recursive nature of MSD sorting may complicate external sorting strategies.

• Adaptability to Partial Key Sorting: • Memory Requirements:

MSD radix sort can be adapted to sort only a portion of the keys. This feature Like LSD radix sort, MSD radix sort can have higher memory requirements, especially
is useful when dealing with datasets where only a specific prefix of the keys when dealing with large datasets. The recursive nature of the algorithm may contribute to
increased memory usage.
needs to be considered for sorting.
1st iteration

Array = {1, 981, 35, 10}

Count = { 1, 2, 0, 0, 0, 1, 0, 0, 0, 0 }
0 1 2 3 4 5 6 7 8
9

Count = { 1, 3, 3, 3, 3, 4, 4, 4, 4, 4 }
0 1 2 3 4 5 6 7 8
9

Array = {10, 001, 981, 35}

2nd iteration

Array = {10, 1, 981, 35}

Count = { 1, 1, 0, 1, 0, 0, 0, 0, 1, 0 }
0 1 2 3 4 5 6 7 8
9

Count = { 1, 2, 2, 3, 3, 3, 3, 3, 4, 4 }
0 1 2 3 4 5 6 7 8
9

Array = {001, 10, 35, 981}

3rd iteration

Array = { 1, 10, 35, 981}

Count = { 3, 0, 0, 0, 0, 0, 0, 0, 0, 1 }
0 1 2 3 4 5 6 7 8
9

Count = { 3, 3, 3, 3, 3, 3, 3, 3, 3, 4 }
0 1 2 3 4 5 6 7 8
9

Array = {1, 10, 35, 981} SORTED!!

!
 Implementation of Radix Sort in Python

def radix_sort(arr): # Updates the count[i] to store the

position of the next occurrence
# Gets the maximum number to know
the number of digits for i in range(1, 10):

max_num = max(arr) count[i] += count[i - 1]

# The output array
exp = 1
i=n-1
# Performs counting sort for every digit
while i >= 0:
while max_num // exp > 0:
index = arr[i] // exp
counting_sort(arr, exp)
output[count[index % 10] - 1] = arr[i]
exp *= 10
count[index % 10] -= 1
def counting_sort(arr, exp):
i -= 1
n = len(arr)
# Copy the output array to the original
output = [0] * n array

count = [0] * 10 for i in range(n):

arr[i] = output[i]
# Counts occurrences of each digit
arr = [170, 45, 75, 90, 802, 24, 2, 66]
for i in range(n):
# Output
index = arr[i] // exp
print("Unsorted Array:", arr)
count[index % 10] += 1
radix_sort(arr)
print("Sorted array:", arr)