Course contentsShow
← Computer Science
Lesson 789 of 2,87218. Sorting AlgorithmsFree lesson

Counting Sort: Implementation

Implementing counting sort with input counting, prefix sum computation, and output placement phases.

Counting Sort: Implementation

You'll learn how to turn the counting sort idea into working code through three distinct phases.

Now that you understand counting sort's basic concept—using a frequency array instead of comparisons—let's implement it step by step.

The Three Phases

Phase 1: Count Input Elements

First, create a counting array sized to accommodate the range of input values. Scan through the input once, incrementing the count for each value you encounter.

def counting_sort(arr, max_val):
    # Phase 1: Count frequencies
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1

Phase 2: Compute Prefix Sums

Transform the count array into a prefix sum array. Each position now holds the cumulative count—telling you where values of that number end in the sorted output.

    # Phase 2: Compute prefix sums
    for i in range(1, len(count)):
        count[i] += count[i - 1]

Analogy: If you're organizing concert tickets by section, prefix sums tell you "Section A fills rows 1–50, Section B fills rows 51–120," etc.

Phase 3: Place Elements in Output

Walk through the input backwards (important for stability!). For each element, check its prefix sum position, place it there in the output array, then decrement that position.

    # Phase 3: Build output array
    output = [0] * len(arr)
    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1
    
    return output

Walking backwards ensures that if two elements have the same value, the one appearing later in the input stays later in the output—preserving stability.

Key Takeaway: Counting sort implementation requires three distinct phases: counting frequencies, computing prefix sums to determine positions, and placing elements backwards into the output array to maintain stability.