Skip to content
Hello Python
Algorithm1 Practice4 Interview

Radix Sort

Apply stable digit-wise passes to sort bounded-width keys without direct comparisons. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Radix Sort when the prompt's constraints and required operations match this shape: Apply stable digit-wise passes to sort bounded-width keys without direct comparisons.

Pybit demonstrates Radix Sort in a professional Python interview workspace.
On this page · Sort One Digit at a Time

Checking your account…

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

Radix Sort Code Labs

Sort One Digit at a Time

Radix sort orders keys by repeated digit passes rather than pairwise comparison. Least-significant-digit sorting begins at the lowest place and preserves earlier digit work through stability.

Keep Each Digit Pass Stable

Items sharing the current digit must retain their prior relative order. Stable buckets or counting placement ensures higher-place passes do not destroy the ordering already established by lower places.

Trace Stable Digit Passes

Reference
def radix_pass_trace(values):
    output=values.copy();trace=[];place=1;maximum=max(output,default=0)
    while maximum//place:
        buckets=[[] for _ in range(10)]
        for value in output:buckets[(value//place)%10].append(value)
        output=[value for bucket in buckets for value in bucket];trace.append(output.copy());place*=10
    return trace
Practice

Implement radix_pass_trace(values). For nonnegative integers, return the list after each stable base-10 digit pass.

Public tests

  • Preserve prior digit order within buckets

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Base and Number of Passes

With base b and d digits, work is O(d(n + b)). A larger base reduces passes but increases bucket memory; count passes from the maximum key representation.

Radix Sort Nonnegative Integers

Reference
def radix_sort(values):
    output=values.copy();place=1;maximum=max(output,default=0)
    while maximum//place:
        buckets=[[] for _ in range(10)]
        for value in output:buckets[(value//place)%10].append(value)
        output=[value for bucket in buckets for value in bucket];place*=10
    return output
Practice

Implement radix_sort(values). Return a sorted copy of nonnegative integers using stable base-10 passes.

Public tests

  • Sort variable digit lengths without mutation

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Handle Signs and Variable Lengths

Missing higher digits act as zero for nonnegative integers. Signed values need a deliberate strategy such as separately sorting magnitudes of negatives and reversing their order; direct digit extraction alone is insufficient.

Explain It in an Interview

Say: “Each stable digit pass refines order without breaking lower-place ties. After every digit of the maximum key, full numeric order is established.” State base, sign domain, stability, and O(d(n + b)) cost.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Radix Sort complete workflowO(d(n + 10))O(d(n + 10))Perform stable base-10 bucket passes from the least significant digit through the maximum value.

Space

O(n + 10) for the focused Sort Nonnegative Integers by Digits implementation.

Assumptions

  • 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.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Radix Sort invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. The resolved region satisfies the target ordering relation.
  3. The unresolved region still contains every item not yet placed.
  4. Perform one stable digit distribution. Preserve this claim after every transition.
  5. Repeat through the maximum digit place. Preserve this claim after every transition.

When To Use Or Avoid Radix Sort

Use It When

  • Use Radix Sort when this precondition is stated or can be proved: The comparison, key domain, stability need, and memory constraints match the selected ordering method.
  • Use it when this maintained state removes repeated work: The resolved region satisfies the target ordering relation.

Choose Another Tool When

  • Avoid Radix Sort when this precondition is absent: The comparison, key domain, stability need, and memory constraints match the selected ordering method.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The comparison, key domain, stability need, and memory constraints match the selected ordering method.

Avoid

def radix_sort(values):
    pass

Use instead

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

Where you will hit this: Sort Nonnegative Integers by Digits(opens in a new tab)

Breaking the state transition

Runs only the ones-place pass and fails on multiple-digit values.

Prevent it: Preserve this proof obligation: The resolved prefix, suffix, rank, digit pass, or bucket remains in its documented final relation.

Avoid

def radix_sort(values):
    buckets=[[] for _ in range(10)]
    for value in values:buckets[value%10].append(value)
    return [x for bucket in buckets for x in bucket]

Use instead

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

Where you will hit this: Sort Nonnegative Integers by Digits(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(d(n + 10)).

Avoid

def radix_sort(values):
    buckets=[[] for _ in range(10)]
    for value in values:buckets[value%10].append(value)
    return [x for bucket in buckets for x in bucket]

Use instead

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

Where you will hit this: Car Fleet(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.