Skip to content
Hello Python
Algorithm1 Practice2 Interview

Bucket Sort

Distribute values into ordered buckets, sort locally, and concatenate under distribution assumptions. 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 Bucket Sort when the prompt's constraints and required operations match this shape: Distribute values into ordered buckets, sort locally, and concatenate under distribution assumptions.

Pybit demonstrates Bucket Sort in a professional Python interview workspace.
On this page · Map Values into Ordered Buckets

Checking your account…

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

Bucket Sort Code Labs

Map Values into Ordered Buckets

Bucket sort partitions a numeric range into ordered regions. If every value in bucket i precedes every value in bucket j for i < j, concatenating sorted buckets is globally sorted.

Choose Bucket Width and Range

The mapping must cover minimum and maximum values without boundary overflow. Bucket width, count, and offset should follow the known domain rather than an unexplained constant.

Trace Bucket Assignments

Reference
def bucket_trace(values,width):
    buckets={};trace=[]
    for value in values:
        index=value//width;buckets.setdefault(index,[]).append(value);trace.append([[key,buckets[key].copy()] for key in sorted(buckets)])
    return trace
Practice

Implement bucket_trace(values,width). Return bucket contents after each nonnegative integer is assigned by value // width.

Public tests

  • Map values by bucket width

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

Sort Within Each Bucket

Buckets are not automatically sorted. Use insertion sort for small expected buckets or the language sort for clarity, then concatenate bucket indexes in order.

Sort Values by Buckets

Reference
def bucket_sort(values,width):
    buckets={}
    for value in values:buckets.setdefault(value//width,[]).append(value)
    result=[]
    for index in sorted(buckets):result.extend(sorted(buckets[index]))
    return result
Practice

Implement bucket_sort(values,width). Return sorted nonnegative integers without mutating input.

Public tests

  • Order buckets then their contents

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

Know When Buckets Degenerate

Expected near-linear behavior depends on a favorable distribution. If all values land in one bucket, inner sorting falls back to O(n log n) or worse. Memory also grows with allocated empty buckets.

Explain It in an Interview

Say: “This mapping preserves cross-bucket order; I sort only within buckets and concatenate them.” State distribution assumptions, treatment of negatives and endpoints, expected cost, and the worst-case degeneration.

Python Version Note

Complexity & Invariants

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

OperationAverageWorstInterview note
Bucket Sort complete workflowO(n + b log b + local sorting)O(n + b log b + local sorting)Use floor-division bucket indexes, sort each small bucket, and concatenate buckets by numeric key.

Space

O(n + b) for the focused Group Integers into Ordered Buckets implementation.

Assumptions

  • Floor division partitions the integers into ordered disjoint ranges. Local sorting orders each range, and increasing bucket keys place every earlier range before every later range.
  • 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 Bucket 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. Map signed integers to deterministic bucket indexes. Preserve this claim after every transition.
  5. Concatenate locally ordered buckets by bucket index. Preserve this claim after every transition.

When To Use Or Avoid Bucket Sort

Use It When

  • Use Bucket 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 Bucket 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 bucket_sort(values, bucket_width):
    pass

Use instead

def bucket_sort(values, bucket_width):
    buckets = {}
    for value in values:
        buckets.setdefault(value // bucket_width, []).append(value)
    result = []
    for index in sorted(buckets):
        result.extend(sorted(buckets[index]))
    return result

Where you will hit this: Group Integers into Ordered Buckets(opens in a new tab)

Breaking the state transition

Uses truncating division and insertion-order buckets, which misorders signed ranges.

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

Avoid

def bucket_sort(values,bucket_width):
    buckets={}
    for value in values:buckets.setdefault(int(value/bucket_width),[]).append(value)
    return [value for bucket in buckets.values() for value in sorted(bucket)]

Use instead

def bucket_sort(values, bucket_width):
    buckets = {}
    for value in values:
        buckets.setdefault(value // bucket_width, []).append(value)
    result = []
    for index in sorted(buckets):
        result.extend(sorted(buckets[index]))
    return result

Where you will hit this: Group Integers into Ordered Buckets(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(n + b log b + local sorting).

Avoid

def bucket_sort(values,bucket_width):
    buckets={}
    for value in values:buckets.setdefault(int(value/bucket_width),[]).append(value)
    return [value for bucket in buckets.values() for value in sorted(bucket)]

Use instead

def bucket_sort(values, bucket_width):
    buckets = {}
    for value in values:
        buckets.setdefault(value // bucket_width, []).append(value)
    result = []
    for index in sorted(buckets):
        result.extend(sorted(buckets[index]))
    return result

Where you will hit this: Sort Characters by Frequency(opens in a new tab)

Reviewed References

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