Radix Sort

Radix Sort organizes numbers by sorting them digit by digit. It starts with the least significant digit (rightmost) and works to the most significant digit (leftmost). Numbers are placed into buckets based on each digit's value, then collected back together in order. This process is repeated for each digit, leading to arr sorted list.

Things to Observe

• Digit by Digit: Notice how the sorting happens in passes, one for each digit place (ones, tens, hundreds, etc.), starting from the rightmost digit.
• Bucketing: In each pass, watch how the numbers are distributed into "buckets" (0-9) based on the value of the current digit. They are then collected back from the buckets in order, preserving the relative order from the previous pass.

Pseudocode

max = largest(arr)

exp = 1

while (max / exp) > 0:

    buckets[0..9] = empty stacks

    for i = 0 to (n - 1):

        d = (arr[i] / exp) % 10

        push arr[i] to buckets[d]

    k = n - 1

    for j = 9 to 0:

        b = buckets[j]

        while b is not empty:

            arr[k] = b.pop()

            k = k - 1

    exp = exp * 10