Q18Data Structures

Radix Sort fundamentally diverges from traditional comparative sorting methodologies (like Quick Sort or Merge Sort). Instead of mathematically comparing the magnitude of entire values against each other, Radix Sort aggressively exploits the structural, positional nature of number systems. It processes the individual digits of every number sequentially, distributing them into corresponding "buckets" (0-9) based on their specific digit value at a given position. Crucially, to maintain overall sequence integrity, Radix Sort rigorously mandates the use of a mathematically stable subroutine sorting algorithm—almost universally Counting Sort—for processing each individual digit column.

1. Algorithmic Overview and Setup

The given unsorted input array sequence is: [329, 457, 657, 839, 436, 720, 355]. Before initiating the sorting loops, the algorithm must precisely determine the maximum value residing within the array to deduce the maximum number of structural digits required. The maximum value here is 839, which consists of exactly three digits ($d=3$). Therefore, the overarching Radix Sort algorithm must execute exactly three discrete sorting passes, strictly processing from the Least Significant Digit (LSD - the "ones" place) progressively toward the Most Significant Digit (MSD - the "hundreds" place).

2. Pass 1: Sorting by the Least Significant Digit (Ones Place)

The algorithm extracts exclusively the final digit (the ones place) from every single element in the array to determine its bucket placement.

• 329 $\to$ Digit: 9
• 457 $\to$ Digit: 7
• 657 $\to$ Digit: 7
• 839 $\to$ Digit: 9
• 436 $\to$ Digit: 6
• 720 $\to$ Digit: 0
• 355 $\to$ Digit: 5

The stable counting sort subroutine now systematically distributes these values into numerical buckets (0-9) strictly based on their extracted digit. - Bucket 0: 720 - Bucket 5: 355 - Bucket 6: 436 - Bucket 7: 457, 657 (The stable sort strictly preserves their original relative order) - Bucket 9: 329, 839

The array is systematically re-assembled by concatenating the buckets sequentially from 0 to 9. Array Post-Pass 1: [720, 355, 436, 457, 657, 329, 839]

3. Pass 2: Sorting by the Middle Digit (Tens Place)

The algorithm advances one position to the left, extracting strictly the middle digit (the tens place) from the newly reorganized array.

• 720 $\to$ Digit: 2
• 355 $\to$ Digit: 5
• 436 $\to$ Digit: 3
• 457 $\to$ Digit: 5
• 657 $\to$ Digit: 5
• 329 $\to$ Digit: 2
• 839 $\to$ Digit: 3

Again, the stable sorting subroutine distributes the values into buckets based on this new extraction. - Bucket 2: 720, 329 - Bucket 3: 436, 839 - Bucket 5: 355, 457, 657

The array is carefully re-assembled from the buckets. Array Post-Pass 2: [720, 329, 436, 839, 355, 457, 657]

4. Pass 3: Sorting by the Most Significant Digit (Hundreds Place)

The algorithm advances to the final structural position, extracting the leading digit (the hundreds place).

• 720 $\to$ Digit: 7
• 329 $\to$ Digit: 3
• 436 $\to$ Digit: 4
• 839 $\to$ Digit: 8
• 355 $\to$ Digit: 3
• 457 $\to$ Digit: 4
• 657 $\to$ Digit: 6

Final distribution into buckets based on the highest-order digit. - Bucket 3: 329, 355 - Bucket 4: 436, 457 - Bucket 6: 657 - Bucket 7: 720 - Bucket 8: 839

The array is sequentially re-assembled for the final time. Final Sorted Array: [329, 355, 436, 457, 657, 720, 839]

By rigorously sorting strictly from the least significant structural positional digit up to the most significant positional digit, the array is systematically organized. The time complexity for this process is firmly bounded at $O(d(n+k))$, where $n$ is the total volume of numbers, $d$ is the maximum number of digit places, and $k$ represents the size of the radix base (10 for standard decimals).