When Values Have Limited Range - Counting Sort: Breaking the Comparison-Based Barrier | OneNoughtOne

0/361

Data Structures & AlgorithmsCounting Sort — Non-Comparison Sorting

Counting Sort: Breaking the Comparison-Based Barrier

LevelIntermediate

Duration55 mins

TopicCounting Sort — Non-Comparison Sorting

1 / 4

When Values Have Limited Range

Breaking the Lower Bound

Throughout our exploration of sorting algorithms—from the simple bubble sort to the sophisticated quick sort—we've operated under an implicit assumption: comparison is the only way to determine ordering. We compare elements pairwise, asking 'Is A less than B?', and from these binary decisions, we construct sorted output.

This assumption leads to a mathematical certainty: no comparison-based sorting algorithm can do better than Ω(n log n) in the worst case. This is proven through decision tree analysis—with n! possible permutations and binary comparisons, log₂(n!) ≈ n log n comparisons are necessary.

But what if we challenged this assumption? What if, under certain conditions, we could sort without comparing elements at all?

The Paradigm Shift

Counting sort represents a fundamental paradigm shift: instead of asking 'Is A less than B?', we ask 'What value is A?' When values come from a bounded, discrete domain, this question reveals everything we need to know about ordering—without a single comparison.

This page explores the crucial precondition that enables this revolutionary approach: the limited range constraint. Understanding when and why this constraint holds is the key to unlocking linear-time sorting.

The Limited Range Insight

Consider a deceptively simple observation: if you know that every element in your array is an integer between 0 and 100, you've gained something profound—you know exactly where each element 'belongs' in the sorted output without comparing it to anything else.

The number 42, by virtue of being 42, belongs after 41 elements that are smaller (0 through 41) and before 58 elements that are larger (43 through 100). No comparison required.

This is direct addressing: the value itself determines position. It's the same principle that makes array indexing O(1)—if you want element 42, you don't search for it, you compute where it is.

Properties of a Limited Range

•Bounded: Values have a known minimum and maximum. We denote the range as k = max - min + 1.
•Discrete: Values are countable (typically integers). We can enumerate every possible value.
•Known a priori: The range is known before sorting begins, not discovered during execution.
•Reasonable size: The range k is small enough that we can allocate an array of size k.

Contrast with Comparison-Based Sorting

Comparison-based sorts like merge sort and quick sort work on any totally ordered set: integers, strings, floating-point numbers, custom objects. They ask only 'Is A ≤ B?' Counting sort sacrifices this generality for speed—it requires integer-like values from a bounded domain.

Formalizing the Constraint

Let's define the limited range constraint precisely. Given an input array A of n elements:

Definition (Limited Range Property): The input satisfies the limited range property if there exist integers min and max such that for all elements A[i]:

min ≤ A[i] ≤ max

We define the range parameter k = max - min + 1, representing the count of distinct possible values.

Critical Insight: The relationship between n (array size) and k (value range) determines whether counting sort is efficient:

If k = O(n): Counting sort achieves O(n) time—faster than any comparison-based sort.
If k = O(n log n): Counting sort ties with comparison sorts.
If k = Ω(n²): Counting sort is slower than comparison sorts.
If k is exponential: Counting sort becomes impractical.

Counting Sort Efficiency vs Range Size
Range k	Counting Sort Time	Comparison Sort Time	Winner
k = 100, n = 10,000	O(10,100) ≈ O(n)	O(n log n) ≈ 130,000 ops	Counting Sort
k = n	O(2n) = O(n)	O(n log n)	Counting Sort
k = n log n	O(n log n)	O(n log n)	Tie
k = n²	O(n²)	O(n log n)	Comparison Sort
k = 2ⁿ (exponential)	Infeasible	O(n log n)	Comparison Sort

The k Factor

Never evaluate counting sort's efficiency without considering k. Saying 'counting sort is O(n)' is incomplete—it's O(n + k). When k >> n, the algorithm degrades catastrophically. The constraint k = O(n) is typically required for counting sort to be advantageous.

Why the Constraint Enables Linear Time

The comparison-based lower bound of Ω(n log n) arises from information theory. With n elements, there are n! possible orderings. Each comparison yields 1 bit of information (yes/no), and distinguishing between n! possibilities requires at least log₂(n!) bits, which is Ω(n log n).

The limited range constraint provides a different source of information: the values themselves. When we know a value is, say, 42, we've gained log₂(k) bits of information in O(1) time—without any comparison.

Comparison-Based Sorting:
─────────────────────────
• Information available: Binary comparisons only
• Bits per comparison: 1
• Bits needed to distinguish n! orderings: log₂(n!) ≈ n log n
• Lower bound: Ω(n log n) comparisons
 
Counting Sort with Range k:
───────────────────────────
• Information available: Each value ∈ [0, k-1]
• Bits per value read: log₂(k)
• Total bits available: n × log₂(k)
 
When k = O(n):
  n × log₂(n) bits available from values alone
  ≈ n log n bits (enough to determine ordering)
  Acquired in O(n) time (reading each value once)
 
Key Insight:
────────────
The values themselves encode the ordering information.
We trade the generality of comparisons for the
directness of value-based positioning.

The direct addressing principle:

Imagine sorting mail into mailboxes numbered 1 through 100. You don't compare letters to each other—you look at the address (the value) and put the letter directly in the corresponding mailbox. This is O(n): one operation per letter, regardless of how many letters exist.

Counting sort applies this same principle. Values become indices, and indices become positions. The 'sorting' is implicit in the structure we build.

Real-World Scenarios with Limited Ranges

The limited range property isn't an artificial constraint—it naturally appears in many practical domains. Recognizing these scenarios is crucial for applying counting sort effectively.

Common Limited-Range Data Types

•Age values: Human ages typically range 0-120. With k ≈ 120, counting sort handles millions of records effortlessly.
•Exam scores: Grades often range 0-100 or 0-1000 (with decimal points scaled to integers). Perfect for counting sort.
•ASCII characters: The 128 standard ASCII values form a small, bounded set. Sorting characters is ideal for counting sort.
•Pixel intensities: In 8-bit grayscale images, each pixel is 0-255. Sorting 10 million pixels by intensity is O(n).
•HTTP status codes: Status codes range roughly 100-599. Sorting log entries by status is trivial with counting sort.
•Categorical encodings: Categories encoded as integers (0 = Red, 1 = Green, 2 = Blue) have tiny ranges.
•Day of year: Values 1-365 (or 366) represent dates within a year—easily countable.
•Small identifiers: User types, privilege levels, product categories—often enumerable with k < 100.

Pattern Recognition

When analyzing a sorting problem, ask: 'What is the range of values?' If the answer is a small constant (like ages or scores) or bounded by O(n), counting sort may outperform comparison sorts dramatically. This single question can transform an O(n log n) operation into O(n).

Transforming Data to Limited Range

Sometimes data doesn't naturally satisfy the limited range property, but can be transformed to do so. This technique, called coordinate compression or discretization, enables counting sort on data that appears unbounded at first glance.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Transform arbitrary integers to a limited range [0, n-1]
 * by mapping each unique value to its rank among all values.
 * 
 * Original:    [1000000, 5, 999999, 5, 1000000]
 * Compressed:  [2, 0, 1, 0, 2]
 * 
 * After compression, k = number of distinct values ≤ n
 */
function coordinateCompress(arr: number[]): {
    compressed: number[];
    decompression: number[];
} {
    // Step 1: Find unique values and sort them
    const uniqueSorted = [...new Set(arr)].sort((a, b) => a - b);
    
    // Step 2: Create value → rank mapping
    const valueToRank = new Map<number, number>();
    uniqueSorted.forEach((val, idx) => valueToRank.set(val, idx));
    
    // Step 3: Compress original array
    const compressed = arr.map(val => valueToRank.get(val)!);
    
    return {
        compressed,           // Use this for counting sort
        decompression: uniqueSorted  // Map rank → original value
    };
}
 
// Example: Sorting with coordinate compression
function sortWithCompression(arr: number[]): number[] {
    const { compressed, decompression } = coordinateCompress(arr);
    
    // Now counting sort works: k = decompression.length ≤ n
    const countingSorted = countingSort(compressed, decompression.length);
    
    // Decompress to get original values
    return countingSorted.map(rank => decompression[rank]);
}

Compression Trade-off

Coordinate compression requires O(n log n) time (to sort unique values), which seems to defeat the purpose. However, it's useful when: (1) you need to sort the same data multiple times with different criteria, (2) counting sort is part of a larger algorithm like radix sort, or (3) the actual values don't matter, only relative order.

Handling Negative Numbers and Non-Zero Bases

The canonical counting sort assumes values in [0, k-1]. Real data often includes negative numbers or arbitrary ranges like [-50, 50] or [1000, 2000]. This requires a simple but critical adjustment: offset normalization.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * Normalize an array with arbitrary range [min, max] to [0, k-1]
 * where k = max - min + 1.
 * 
 * Example:
 *   Input range: [-5, 5]  →  Normalized range: [0, 10]
 *   Value -5 → 0, Value 0 → 5, Value 5 → 10
 */
function normalizeRange(arr: number[]): {
    normalized: number[];
    offset: number;
    rangeSize: number;
} {
    const min = Math.min(...arr);
    const max = Math.max(...arr);
    const rangeSize = max - min + 1;
    
    // Subtract min to shift all values to [0, k-1]
    const normalized = arr.map(val => val - min);
    
    return {
        normalized,
        offset: min,      // Store to denormalize later
        rangeSize
    };
}
 
// Complete counting sort with offset handling
function countingSortWithOffset(arr: number[]): number[] {
    if (arr.length === 0) return [];
    
    const { normalized, offset, rangeSize } = normalizeRange(arr);
    
    // Standard counting sort on normalized values
    const count = new Array(rangeSize).fill(0);
    for (const val of normalized) {
        count[val]++;
    }
    
    // Build output
    const output: number[] = [];
    for (let val = 0; val < rangeSize; val++) {
        // Add 'offset' back to denormalize
        for (let i = 0; i < count[val]; i++) {
            output.push(val + offset);
        }
    }
    
    return output;
}
 
// Test with negative numbers
console.log(countingSortWithOffset([-3, 5, 0, -1, 5, -3]));
// Output: [-3, -3, -1, 0, 5, 5]

Offset Must Be Consistent

When normalizing, find min and max once at the start. Using different offsets during counting and output phases corrupts the result. This is a common implementation bug.

When the Limited Range Constraint Breaks Down

Understanding when counting sort should not be used is as important as knowing when it excels. The limited range property can fail in several ways, each demanding a different response.

Scenarios Where Counting Sort Fails

•Floating-point numbers: Values like 3.14159 can't be directly indexed. The 'range' between 0.0 and 1.0 is infinite. Use comparison sorts or convert to integers (e.g., multiply by 1000, floor).
•Strings: Even short strings have astronomical 'ranges'. 'aa' to 'zz' is 676 combinations, but general strings span 26^length possibilities. Use radix sort for fixed-length strings.
•64-bit integers with full range: Range of 0 to 2^64-1 requires an 18-exabyte count array. Clearly infeasible. Use radix sort (digit-by-digit) or comparison sorts.
•Arbitrary objects: Custom objects with complex comparison functions can't be indexed by value. You need comparison-based sorting.
•Sparse large ranges: If values are in [0, 1,000,000] but only 100 are present, you waste 999,900 array slots. Coordinate compression or hash-based approaches work better.

Decision Heuristic

Ask two questions: (1) Can values be directly used as array indices? (2) Is k ≤ n (or at least O(n))? If both answers are yes, counting sort is likely optimal. Otherwise, consider radix sort, bucket sort, or comparison-based alternatives.

The Range Parameter in Complexity Analysis

Counting sort's complexity is O(n + k), where n is the input size and k is the range. This two-variable complexity requires careful analysis—you can't simply say 'counting sort is O(n)'.

Counting Sort Complexity: O(n + k)
═══════════════════════════════════
 
Phase 1: Initialize count array of size k
         → O(k) operations
 
Phase 2: Count occurrences (iterate through input)
         → O(n) operations
 
Phase 3: Compute cumulative counts
         → O(k) operations
 
Phase 4: Build output array (iterate through input)
         → O(n) operations
 
Total: O(k) + O(n) + O(k) + O(n) = O(n + k)
 
═══════════════════════════════════
 
Space Complexity: O(n + k)
  • Count array: O(k)
  • Output array: O(n)
  • Total auxiliary: O(n + k)
 
═══════════════════════════════════
 
Simplification Cases:
  • k = O(n)   → O(n + n) = O(n)     [Linear!]
  • k = O(1)   → O(n + 1) = O(n)     [Even better!]
  • k = n²     → O(n + n²) = O(n²)   [Quadratic...]
  • k = 2ⁿ     → Exponential         [Disaster]

Simplification is Context-Dependent

When k is a known constant (like k = 256 for byte values), we can simplify O(n + k) to O(n). But in algorithm analysis and competitive programming, always state the full O(n + k) complexity unless k is explicitly bounded.

Summary: The Foundation of Non-Comparison Sorting

The limited range property is the gateway to linear-time sorting. Before applying counting sort, you must verify this precondition and understand its implications.

Key Takeaways

•The limited range property enables direct addressing: Values become indices, bypassing comparison entirely.
•The range k must be manageable: Counting sort is efficient when k = O(n); it degrades when k >> n.
•Many real-world domains have natural bounded ranges: Ages, scores, characters, pixels, status codes.
•Coordinate compression can artificially create bounded ranges: Transform any n distinct values to [0, n-1].
•Handle negative numbers with offset normalization: Shift the range to start at zero.
•Complexity is O(n + k), not just O(n): Always state both parameters in analysis.

Page Complete

You now understand the fundamental precondition for counting sort: the limited range property. This insight—that bounded, discrete values can be sorted without comparison—is the conceptual breakthrough that enables all non-comparison sorting algorithms. Next, we'll explore exactly how counting sort leverages this property through its counting phase.