# Key Indexed Counting

# Key Indexed Counting

Key indexed counting is a stable linear time sorting method for items with small integer keys. It generalizes counting sort by separating keys from records and placing records directly into their correct index range.

This form is widely used in string sorting and radix-based pipelines.

## Problem

Given an array $A$ of records, where each record has a key in range $[0, k)$, reorder the array so that records are sorted by key while preserving stability.

## Idea

Instead of reconstructing values, compute the starting index for each key and place each record directly into its correct position.

Let:

* $C[i]$ store the number of keys equal to $i$
* Transform $C$ into starting indices using prefix sums
* Place each element using its key as an index

## Algorithm

```id="d7k2pa"
key_indexed_counting(A, k):
    count = [0] * (k + 1)

    for item in A:
        count[item.key + 1] += 1

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

    aux = [None] * len(A)

    for item in A:
        idx = count[item.key]
        aux[idx] = item
        count[item.key] += 1

    return aux
```

## Example

Let records be:

$$
A = [(2,a), (1,b), (2,c), (0,d)]
$$

Keys:

$$
[2, 1, 2, 0]
$$

After sorting:

$$
[(0,d), (1,b), (2,a), (2,c)]
$$

Relative order among equal keys is preserved.

## Correctness

The prefix sum phase computes disjoint index intervals for each key. Each record is placed exactly once into its assigned interval. Because insertion follows input order, stability holds.

## Complexity

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

Space:

$$
O(n + k)
$$

## Notes

* The shift by +1 in counting simplifies prefix sum logic
* The algorithm separates keys from records, unlike basic counting sort
* Often used as a primitive in LSD and MSD radix sort

## When to Use

Use key indexed counting when:

* sorting structured records by small integer keys
* stability is required
* used inside radix or string sorting pipelines

## Implementation (Go)

```id="g2r9vn"
type Item struct {
	Key int
	Val any
}

func KeyIndexedCounting(a []Item, k int) []Item {
	count := make([]int, k+1)

	for _, item := range a {
		count[item.Key+1]++
	}

	for i := 1; i <= k; i++ {
		count[i] += count[i-1]
	}

	aux := make([]Item, len(a))

	for _, item := range a {
		idx := count[item.Key]
		aux[idx] = item
		count[item.Key]++
	}

	return aux
}
```