LSD-Radix-Sort

• Time cost: $\Theta (m(n+R))$
• Auxiliary space: $\Theta (n+R)$
• Loop invariant: $A$ is sorted with respect to digits $d$,…,$m$ of each entry.

Time Complexity

Best Case: $\Theta (n)$ Worst Case: $\Theta (nm)$

Related

• MSD-Radix Sort
• Trie

Questions

Why???

The question is basically asking for the array after 1 iteration of LSD Radix Sort. Here, the base (radix) is $R=100$. Since the base is 100, we can represent it as 2 base-10 digits, and it’s just as you would imagine: 39 < 63 < 84. Since these two-digit numbers are technically classified as 1 digit in base 100, when we perform the first iteration of LSD Radix Sort, the digits that we perform Bucket Sort on are [84], [39], [63], [39]. Since 939 comes before 439 in the original array, and since bucket sort is stable (first element in is the first element out), when we pop out all the elements at the end of bucket sort, the final array that we obtain is [939, 439, 763, 284].