Stable Counting Sort

Stable counting sort extends counting sort by preserving the relative order of equal elements. This property is required in multi-pass algorithms such as radix sort.

The algorithm uses prefix sums to compute exact output positions for each element.

Problem

Given an array $A$ of $n$ elements with integer keys in range $[0, k]$ , produce a sorted array while preserving the relative order of elements with equal keys.

Idea

Count occurrences, convert counts into cumulative positions, then place elements into the correct position from right to left.

Let:

$C[i]$ store the number of elements $\le i$
This gives the final position of each key

Algorithm

stable_counting_sort(A, k):
    C = [0] * (k + 1)

    for x in A:
        C[x] += 1

    for i in range(1, k + 1):
        C[i] += C[i - 1]

    B = [0] * len(A)

    for i from length(A) - 1 down to 0:
        x = A[i]
        C[x] -= 1
        B[C[x]] = x

    return B

Example

Let:

A = [4, 2, 2, 8, 3, 3, 1]

Counts:

value	count
1	1
2	2
3	2
4	1
8	1

Prefix sums:

value	position
1	1
2	3
3	5
4	6
8	7

Final sorted array:

[1, 2, 2, 3, 3, 4, 8]

Stability

The reverse traversal ensures that later occurrences of equal keys are placed later in the output. This preserves the original order.

Correctness

Each element is assigned a unique position based on cumulative counts. The mapping from input to output is one-to-one and order preserving for equal keys.

Complexity

component	cost
counting	$O(n)$
prefix sum	$O(k)$
placement	$O(n)$
total	$O(n + k)$

Space:

O(n + k)

When to Use

Use stable counting sort when:

stable ordering matters
keys lie in a small integer range
used as a subroutine in radix sort
deterministic linear time is required

Implementation (Python)

def stable_counting_sort(a, k):
    count = [0] * (k + 1)

    for x in a:
        count[x] += 1

    for i in range(1, k + 1):
        count[i] += count[i - 1]

    output = [0] * len(a)

    for i in range(len(a) - 1, -1, -1):
        x = a[i]
        count[x] -= 1
        output[count[x]] = x

    return output