Past exam question: 2072 Ashwin (Regular), Q10
Open in the Padhaiko appQuestion
Define a radix sort with its algorithm. Trace the steps to sort the following set of data using merge sort: 85, 76, 46, 92, 30, 41 and 12.
Solution
Definition and Algorithm of Radix Sort: Radix sort is a non-comparative, stable sorting algorithm that sorts integer keys digit by digit from the Least Significant Digit (LSD) to the Most Significant Digit (MSD) using a stable distribution/counting sort at each digit position. For -digit keys in base , time complexity is .
Algorithm RADIX_SORT(A, n, d):
1. For digitPos = 0 to d - 1:
Initialize 10 empty buckets B[0..9]
For i = 0 to n - 1:
digit = (A[i] / 10^digitPos) % 10
Append A[i] to B[digit]
Concatenate B[0], B[1], ..., B[9] back into AMerge Sort Trace on [85, 76, 46, 92, 30, 41, 12]:
- Divide Phase (Recursive Splitting):
[85, 76, 46, 92, 30, 41, 12]- Left:
[85, 76, 46, 92][85, 76]and[46, 92][85], [76], [46], [92] - Right:
[30, 41, 12][30, 41]and[12][30], [41], [12]
- Conquer Phase (Bottom-Up Merging):
- Merge
[85]and[76][76, 85] - Merge
[46]and[92][46, 92] - Merge
[30]and[41][30, 41] - Merge
[76, 85]and[46, 92][46, 76, 85, 92] - Merge
[30, 41]and[12][12, 30, 41] - Final merge of
[46, 76, 85, 92]and[12, 30, 41][12, 30, 41, 46, 76, 85, 92].
- Merge
Answer:
- Radix Sort: Sorts keys digit-by-digit (LSD to MSD) in time using stable buckets.
- Merge Sort Output:
12, 30, 41, 46, 76, 85, 92.