Skip to content
Hello Python
Algorithm1 Practice1 Interview

Counting Sort

Count bounded integer keys and reconstruct order in time proportional to input plus key range. 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 Counting Sort when the prompt's constraints and required operations match this shape: Count bounded integer keys and reconstruct order in time proportional to input plus key range.

Pybit demonstrates Counting Sort in a professional Python interview workspace.
On this page · Count a Bounded Key Domain

Checking your account…

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

Counting Sort Code Labs

Count a Bounded Key Domain

Counting sort replaces comparisons with a frequency array indexed by keys. It is appropriate only when keys map to a reasonably small known integer domain.

Turn Counts into Output

For plain values, emit each key its recorded number of times. This costs O(n + k), where k is the domain size, even if few keys occur.

Trace Frequency Counts

Reference
def count_trace(values,maximum):
    counts=[0]*(maximum+1);trace=[]
    for value in values:counts[value]+=1;trace.append(counts.copy())
    return trace
Practice

Implement count_trace(values,maximum). Return the count array after each nonnegative value.

Public tests

  • Increment exactly one domain slot

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

Preserve Stability with Positions

Convert counts to cumulative end positions, traverse records from right to left, decrement the key’s position, and place the record there. Reverse traversal preserves equal-key input order.

Stable Counting Sort Records

Reference
def stable_counting_sort(records,maximum):
    counts=[0]*(maximum+1)
    for key,_ in records:counts[key]+=1
    for index in range(1,len(counts)):counts[index]+=counts[index-1]
    output=[None]*len(records)
    for record in reversed(records):
        key=record[0];counts[key]-=1;output[counts[key]]=record.copy()
    return output
Practice

Implement stable_counting_sort(records,maximum). Sort [key,label] by nonnegative key while preserving equal-key order.

Public tests

  • Use cumulative output positions

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

Choose Counting Sort or Comparison Sort

Choose counting sort when k is comparable to n and keys are bounded integers. Use comparison sorting when the domain is huge, sparse, unknown, or keys need arbitrary ordering. Offset indexes deliberately for negative keys.

Explain It in an Interview

Say: “The count array summarizes the bounded key domain. Cumulative counts locate output positions, and reverse placement preserves stability.” State O(n + k) time and O(n + k) space rather than calling it simply linear.

Python Version Note

Complexity & Invariants

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

OperationAverageWorstInterview note
Counting Sort complete workflowO(n + r)O(n + r)Count the offset integer domain and expand frequencies from the minimum through maximum.

Space

O(r) for the focused Sort a Bounded Integer Range implementation.

Assumptions

  • Every input increments exactly one decoded integer bucket. Emitting buckets in increasing offset order with exact frequency preserves the multiset and sorts it.
  • 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 Counting 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. Offset counts by the minimum value. Preserve this claim after every transition.
  5. Emit every value exactly its frequency. Preserve this claim after every transition.

When To Use Or Avoid Counting Sort

Use It When

  • Use Counting 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 Counting 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 counting_sort(values):
    pass

Use instead

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

Where you will hit this: Sort a Bounded Integer Range(opens in a new tab)

Breaking the state transition

Emits each distinct value once and loses duplicate multiplicity.

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

Avoid

def counting_sort(values):
    if not values:return []
    low=min(values); counts=[0]*(max(values)-low+1)
    for value in values:counts[value-low]+=1
    return [low+i for i,count in enumerate(counts) if count]

Use instead

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

Where you will hit this: Sort a Bounded Integer Range(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 + r).

Avoid

def counting_sort(values):
    if not values:return []
    low=min(values); counts=[0]*(max(values)-low+1)
    for value in values:counts[value-low]+=1
    return [low+i for i,count in enumerate(counts) if count]

Use instead

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

Where you will hit this: Friends of Appropriate Ages(opens in a new tab)

Reviewed References

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