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.

01 Explore How It Works

Interactive Step-by-Step

HOVER OR SCROLL

Counting Sort · non-comparison

계수 정렬을 시작합니다. 비교 없이 값의 빈도를 세어 O(n+k)에 정렬하는 비교 제외(non-comparison) 알고리즘입니다.

Logic Node1 / 10

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

02 Understand It Simply

For Everyone

🔑Analogy

Tally how many times each number appears, then lay them back out by those counts.

💡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