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

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

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