Group Integers into Ordered Buckets

Practice Exercise Intermediate Medium Array Hash Map Bucket Sort

Checking your account…

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 bucket_sort(values, bucket_width). bucket_width is positive. Return a new ascending list, supporting negative integers. You may call sorted only inside individual buckets, not on the whole input.

Starter code

def bucket_sort(values, bucket_width):
    pass

Test cases

signed-buckets

{
  "args": [
    [
      7,
      -1,
      3,
      -4,
      8
    ],
    3
  ]
}

Expected: [-4,-1,3,7,8]

one-bucket

{
  "args": [
    [
      3,
      1,
      2
    ],
    10
  ]
}

Expected: [1,2,3]

Wizard outline

Step 1: Define the empty distribution
Return no buckets for no values. Distribution starts from an empty mapping and must not invent output.
Step 2: Distribute with floor division
Place signed integers into stable bucket indexes. Python // with a positive width preserves ordered, non-overlapping numeric ranges even below zero.
Step 3: Combine buckets by numeric order
Complete sorting across signed bucket ranges. Every value in a smaller bucket index is no greater than values in a later bucket after local sorting.

Footguns and prerequisites

Truncating division toward zero groups negative values incorrectly.
Iterating dictionary insertion order does not guarantee numeric bucket order.
functions
lists and tuples
control flow

Reviewed references

Python Mapping Types — dict

Recommended approach and implementation

Use floor-division bucket indexes, sort each small bucket, and concatenate buckets by numeric key.

Why it works: 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.

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