Count how many times each value occurs and calculate its output positions directly. For integers in a small range, this can outperform comparison sorting.

A simulator showing counting, prefix sums, and placement in counting sort

Play or step through the algorithm, or seek with the slider. The lower row is out, the output array; count is shown below on the right.

TimeO(n + k)

Extra spaceO(n + k)

StableYes

Value comparisonsZero

RequirementSmall-range integers

Prefix sums determine positions

After prefix summation, count[v] gives the number of values at most v and therefore the end of v's output region. Scanning the input backward and filling from each region's end preserves the order of equal values. This stability allows counting sort to serve as a digit-sorting stage in radix sort.

k is the value range. A very broad range, such as 0 to one billion, makes the count array impractical.

Many values, a narrow range

For ten million integers bounded by ten thousand, accumulating frequencies and printing them in value order can save both time and memory compared with storing and sorting every item.

import sys
input = sys.stdin.readline
cnt = [0] * 10001
for _ in range(int(input())):
    cnt[int(input())] += 1
for v in range(10001):
    if cnt[v]:
        sys.stdout.write((str(v) + '\n') * cnt[v])