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