# Stable Counting Sort

# 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

```id="w8p2qa"
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)

```id="m3q9fj"
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
```