# Counting Sort with Negative Keys

# Counting Sort with Negative Keys

Counting sort normally assumes keys lie in a nonnegative range. This variant handles negative integers by shifting all values so that the minimum becomes zero, then applying standard counting sort.

## Problem

Given an array $A$ of $n$ integers that may include negative values, sort the array.

Let:

$$
\min = \min(A),\quad \max = \max(A)
$$

## Idea

Shift every value by $-\min$ so all keys become nonnegative:

$$
x' = x - \min
$$

Then apply counting sort on $x'$ in range $[0, \max - \min]$, and map back if needed.

## Algorithm

```text id="c9p2qa"
counting_sort_with_negatives(A):
    lo = minimum(A)
    hi = maximum(A)
    k = hi - lo + 1

    count = [0] * k

    for x in A:
        count[x - lo] += 1

    i = 0
    for v from 0 to k - 1:
        while count[v] > 0:
            A[i] = v + lo
            i += 1
            count[v] -= 1

    return A
```

## Example

Let:

$$
A = [-3, -1, -2, 0, 2, 1]
$$

Shift:

$$
lo = -3
$$

Mapped values:

$$
[0, 2, 1, 3, 5, 4]
$$

After sorting and shifting back:

$$
[-3, -2, -1, 0, 1, 2]
$$

## Correctness

The transformation $x' = x - \min$ is a bijection between the original values and the shifted values. It preserves order:

$$
x_1 < x_2 \iff x_1' < x_2'
$$

Counting sort correctly orders the shifted values, so mapping back yields the correct sorted order of the original values.

## Complexity

Let:

* $n$ be the number of elements
* $k = \max - \min + 1$ be the range size

Time:

$$
O(n + k)
$$

Space:

$$
O(k)
$$

## Properties

| property           | value                        |
| ------------------ | ---------------------------- |
| stable             | yes, if using stable variant |
| in place           | no                           |
| comparison based   | no                           |
| supports negatives | yes                          |

## When to Use

Use this variant when:

* keys include negative integers
* the value range is small
* linear-time sorting is desired

Avoid when the range $k$ is large compared to $n$, since memory usage becomes inefficient.

## Implementation

```python id="z2m7qa"
def counting_sort_with_negatives(a):
    if not a:
        return a

    lo = min(a)
    hi = max(a)
    k = hi - lo + 1

    count = [0] * k

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

    i = 0
    for v in range(k):
        while count[v] > 0:
            a[i] = v + lo
            i += 1
            count[v] -= 1

    return a
```