Skip to content
Hello Python

Sort Nonnegative Integers by Digits

Practice ExerciseIntermediateMediumArrayRadix Sort

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement radix_sort(values). values contains nonnegative integers. Return a new ascending list without sorted or list.sort.

Starter code

def radix_sort(values):
    pass
Test cases

multiple-digits

{
  "args": [
    [
      170,
      45,
      75,
      90,
      802,
      24,
      2,
      66
    ]
  ]
}

Expected: [2,24,45,66,75,90,170,802]

zeros

{
  "args": [
    [
      0,
      10,
      0,
      1
    ]
  ]
}

Expected: [0,0,1,10]

Wizard outline
  1. Step 1: Define an empty digit stream

    Return [] before reading a maximum. The number of passes depends on a maximum that empty input does not have.

  2. Step 2: Run one stable digit pass

    Order values whose only significant digit is the ones place. Appending to digit buckets and draining buckets in order is stable.

  3. Step 3: Advance through every digit place

    Complete stable sorting for different magnitudes. After place p, values are ordered by their lowest p digits; stability preserves that order while the next digit is added.

Footguns and prerequisites
  • An unstable digit pass destroys ordering established by earlier digits.
  • Stopping before the maximum place leaves large values unordered.
  • functions
  • lists and tuples
  • control flow
Reviewed references
Recommended approach and implementation

Perform stable base-10 bucket passes from the least significant digit through the maximum value.

Why it works: Inductively each stable pass orders values by one more low-order digit while preserving prior digit order. After the highest significant place, all digits determine numeric order.

def radix_sort(values):
    result = list(values)
    if not result:
        return result
    place = 1
    maximum = max(result)
    while place <= maximum:
        buckets = [[] for _ in range(10)]
        for value in result:
            buckets[(value // place) % 10].append(value)
        result = [value for bucket in buckets for value in bucket]
        place *= 10
    return result