Sort a Bounded Integer Range

Practice Exercise Intermediate Medium Array Counting 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 counting_sort(values). Return all integers in ascending order, including negatives and duplicates, without sorted or list.sort.

Starter code

def counting_sort(values):
    pass

Test cases

negative-duplicates

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

Expected: [-1,-1,2,3]

single-range

{
  "args": [
    [
      4,
      4
    ]
  ]
}

Expected: [4,4]

Wizard outline

Step 1: Define an empty value range
Return an empty independent result. Minimum and maximum are undefined until non-empty input is established.
Step 2: Count with a minimum offset
Represent negative and positive values in one compact count array. value - minimum maps the full closed integer range to zero-based indexes.
Step 3: Reconstruct the ordered multiset
Emit gaps, negatives, and duplicates correctly. Increasing count indexes correspond exactly to increasing original values.

Footguns and prerequisites

Using values directly as indexes breaks on negatives.
Emitting each present key once loses duplicates.
functions
lists and tuples
control flow

Reviewed references

Python More on Lists

Recommended approach and implementation

Count the offset integer domain and expand frequencies from the minimum through maximum.

Why it works: Every input increments exactly one decoded integer bucket. Emitting buckets in increasing offset order with exact frequency preserves the multiset and sorts it.

def counting_sort(values):
    if not values:
        return []
    low, high = min(values), max(values)
    counts = [0] * (high - low + 1)
    for value in values:
        counts[value - low] += 1
    result = []
    for offset, frequency in enumerate(counts):
        result.extend([low + offset] * frequency)
    return result