Algorithm Guidecomplexity: O(n + k)

Counting Sort

A non-comparison algorithm that sorts by counting value frequencies. When the value range k is limited, it sorts stably in linear O(n+k) time.

01Counting Sort

Explore How It Works

Starting counting sort. Instead of comparing values, just count how many times each one appears — O(n+k).

Phase 1 · counting. Scan the array once and note in the table how often each value appears.

Counting is done. 20 · 30 · 40 appear twice each, 60 · 70 once each — all eight are recorded.

Phase 2 · assigning places. Adding up the counts of the preceding values fixes where each value's run ends.

20 runs through position 2, 30 through 4, 40 through 6 — that fixes the last slot each value takes.

Phase 3 · placing. Scan the original from the back, put each value in its slot, and pull that slot one step forward.

Working from the back, 30 · 40 · 60 move into the slots assigned to them.

20 · 30 · 70 take their places. Among equal values, the one that started later stays later.

Moving the remaining 20 and 40 finishes the placement.

Sorted · 20 20 30 30 40 40 60 70. Not a single comparison was made, and equal values kept their original order.

Live Python

1def counting_sort(arr):

# k: max+1 = 71

2 k = max(arr) + 1

3 count = [0] * k

4 for v in arr:

5 count[v] += 1

7 for i in range(1, k):

8 count[i] += count[i - 1]

10 output = [0] * len(arr)

11 for i in range(len(arr) - 1, -1, -1):

12 output[count[arr[i]] - 1] = arr[i]

13 count[arr[i]] -= 1

14 return output

1 / 10

02 Understand It Simply

For Everyone

🔑How It Works

Counts how often each value occurs, accumulates the counts, and uses them as positions. It never compares, so with a narrow value range it runs in O(n).

💡In Plain Words

Counts occurrences and uses a prefix sum to place values.

No comparisons and O(n+k) fast — but the value range must be narrow.

📍Where It's Used

–Integer / narrow-range data
–the inner step of radix sort

03 Python Implementation

A clean, readable reference implementation of the core logic of Counting Sort.

core_implementation.py

def counting_sort(arr):
    k = max(arr) + 1
    count = [0] * k
    for v in arr:
        count[v] += 1
    
    for i in range(1, k):
        count[i] += count[i - 1]
    
    output = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1
    return output

04 Frequently Asked Questions

FAQ

What is Counting Sort?+

A non-comparison algorithm that sorts by counting value frequencies. When the value range k is limited, it sorts stably in linear O(n+k) time.

What is the time complexity of Counting Sort?+

The time complexity of Counting Sort is O(n + k). Follow the step-by-step visualization to see exactly why.

Where is Counting Sort used?+

Integer / narrow-range data, the inner step of radix sort.

What's a simple analogy for Counting Sort?+

Counts how often each value occurs, accumulates the counts, and uses them as positions. It never compares, so with a narrow value range it runs in O(n).

→ Sorting — see allRelated