AlgoVerse

Radix sort

Sort the numbers digit by digit, starting from the ones digit, with a stable counting sort; after the last digit the whole array is sorted.

Radix sort sorts the numbers digit by digit, starting from the least significant digit (the ones). Each pass is a counting sort on that digit (only ten possible values: 0 to 9).

Read the full explanation ↓
Input:
n=7PDF export

Seven three-digit numbers: three passes for the ones, tens and hundreds digits.

  1. def radix_sort(a):
  2. exp = 1
  3. while max(a) // exp > 0:
  4. a = sort_by_digit(a, exp)
  5. exp = exp * 10
  6. return a
  9. def sort_by_digit(a, exp):
  10. count = [0] * 10
  11. for x in a:
  12. d = (x // exp) % 10
  13. count[d] = count[d] + 1
  14. for d in range(1, 10):
  15. count[d] = count[d] + count[d - 1]
  16. out = [0] * len(a)
  17. for j in range(len(a) - 1, -1, -1):
  18. d = (a[j] // exp) % 10
  19. count[d] = count[d] - 1
  20. out[count[d]] = a[j]
  21. return out

Invariant: After sorting by the digit at exp, the array is sorted by the number formed by its last digits up to exp.

Start

3290457165728393436472053556

Local variables

Orange = changed in this step

a list

329457657839436720355

Call stack

  1. radix_sort()line 1
Step 1 of 235
Black = pass_done · Orange = key stepcount: 0/21 · place: 0/21 · pass_done: 0/3

    How the work grows with input size

    Average of 12 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • place
    • current input (n=7)
    020406046810121416n = number of itemsplace
    Show as a table
    nplace
    412
    618
    824
    1030
    1236
    1442
    1648
    Explanation

    The idea

    Radix sort sorts the numbers digit by digit, starting from the least significant digit (the ones). Each pass is a counting sort on that digit (only ten possible values: 0 to 9).

    Why start with the ones?

    The key is that every pass is stable. After the ones pass, the numbers are sorted by their ones digit. The tens pass sorts them by the tens digit, and because it is stable, numbers with equal tens digits keep their ones order. So after the tens pass the array is sorted by its last two digits, and so on up to the last digit.

    Cost

    For d digits: O(d·(n + 10)). When the number of digits is fixed, the time is linear, better than n log n.

    What to watch in the trace

    • Use the "every loop round" detail level to see only the end of each pass, and follow the order of the bars after each digit.
    • On the "textbook-style example", after the ones pass the numbers are sorted by their last digit (720, 355, 436, …).