Data Structures & AlgorithmsCounting Sort — Non-Comparison Sorting

Counting Sort: Breaking the Comparison-Based Barrier

LevelIntermediate

Duration55 mins

TopicCounting Sort — Non-Comparison Sorting

2 / 4

Counting Occurrences

The Heart of the Algorithm

With the limited range property established, we now turn to how counting sort exploits this constraint. The answer lies in a deceptively simple idea: instead of rearranging elements directly, we count how many elements have each value.

This count—stored in an auxiliary array—contains everything we need to reconstruct the sorted output. The counting phase is where the magic happens, transforming an unsortable mess into structured information from which order emerges.

The Counting Insight

If you know there are exactly 3 zeros, 5 ones, and 2 twos, you know the sorted output without computing it: [0, 0, 0, 1, 1, 1, 1, 1, 2, 2]. The counts encode the result. Counting sort is, at its core, this observation made algorithmic.

The Count Array Concept

The count array (also called the histogram or frequency array) is an auxiliary data structure of size k, where k is the range of input values. Each index i in the count array holds the number of elements in the input that have value i.

Definition: Given input array A of n elements with values in [0, k-1], the count array C of size k satisfies:

C[i] = |{j : A[j] = i}|

In words: C[i] equals the count of elements in A that equal i.

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
/**
 * Build a count array from input values.
 * 
 * Example:
 *   Input: [2, 0, 2, 3, 1, 0, 2]
 *   Range: 0 to 3 (k = 4)
 *   
 *   Count Array:
 *     Index 0: count of 0s → 2
 *     Index 1: count of 1s → 1
 *     Index 2: count of 2s → 3
 *     Index 3: count of 3s → 1
 *     
 *   C = [2, 1, 3, 1]
 */
function buildCountArray(arr: number[], k: number): number[] {
    // Initialize count array with zeros
    const count = new Array(k).fill(0);
    
    // Single pass through input: O(n)
    for (const value of arr) {
        count[value]++;  // Direct addressing: value IS the index
    }
    
    return count;
}
 
// Example execution
const input = [2, 0, 2, 3, 1, 0, 2];
const k = 4;  // Values range from 0 to 3
const counts = buildCountArray(input, k);
console.log(counts);  // [2, 1, 3, 1]
 
// Verify: sum of counts equals array length
console.log(counts.reduce((a, b) => a + b));  // 7 (correct!)

Direct Addressing in Action

Notice count[value]++. The value itself becomes the index. This is direct addressing—no comparison, no search, just immediate access. This single line is why counting sort bypasses the comparison-based lower bound.

Visualizing the Counting Process

Let's trace through the counting process step by step to build intuition.

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
Input Array: [2, 0, 2, 3, 1, 0, 2]
Range k = 4 (values 0, 1, 2, 3)
 
Initial Count Array: [0, 0, 0, 0]
                      ↑  ↑  ↑  ↑
                      0  1  2  3
 
Step 1: Process A[0] = 2
        count[2]++
        Count: [0, 0, 1, 0]     ← One 2 seen
 
Step 2: Process A[1] = 0
        count[0]++
        Count: [1, 0, 1, 0]     ← One 0 seen
 
Step 3: Process A[2] = 2
        count[2]++
        Count: [1, 0, 2, 0]     ← Two 2s seen
 
Step 4: Process A[3] = 3
        count[3]++
        Count: [1, 0, 2, 1]     ← One 3 seen
 
Step 5: Process A[4] = 1
        count[1]++
        Count: [1, 1, 2, 1]     ← One 1 seen
 
Step 6: Process A[5] = 0
        count[0]++
        Count: [2, 1, 2, 1]     ← Two 0s seen
 
Step 7: Process A[6] = 2
        count[2]++
        Count: [2, 1, 3, 1]     ← Three 2s seen
 
Final Count Array: [2, 1, 3, 1]
 
Interpretation:
  • 2 elements have value 0
  • 1 element has value 1
  • 3 elements have value 2
  • 1 element has value 3
 
Sorted output (by reading counts): [0, 0, 1, 2, 2, 2, 3]

One Pass, Complete Information

After a single O(n) pass, we know exactly how many of each value exist. This information is sufficient to produce sorted output—we've essentially 'sorted' the data by categorizing it.

Simple Counting Sort (Non-Stable Version)

The most straightforward counting sort directly reconstructs the sorted output from the count array. This version works perfectly for sorting bare integers but is not stable—it doesn't preserve the relative order of equal elements.

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
/**
 * Simple Counting Sort: Sort integers using count-based reconstruction.
 * 
 * Algorithm:
 * 1. Build count array: count[i] = number of elements equal to i
 * 2. Reconstruct: output count[i] copies of value i, for each i
 * 
 * Time: O(n + k)
 * Space: O(k) for count array + O(n) for output = O(n + k)
 * Stability: NOT STABLE
 */
function simpleCountingSort(arr: number[], k: number): number[] {
    if (arr.length === 0) return [];
    
    // Phase 1: Build count array - O(k) init + O(n) counting
    const count = new Array(k).fill(0);
    for (const value of arr) {
        count[value]++;
    }
    
    // Phase 2: Reconstruct sorted output - O(n + k)
    const output: number[] = [];
    for (let value = 0; value < k; value++) {
        // Add 'count[value]' copies of 'value' to output
        for (let i = 0; i < count[value]; i++) {
            output.push(value);
        }
    }
    
    return output;
}
 
// Example usage
const unsorted = [4, 2, 2, 8, 3, 3, 1];
const k = 9;  // Values range 0-8
const sorted = simpleCountingSort(unsorted, k);
console.log(sorted);  // [1, 2, 2, 3, 3, 4, 8]

Why Non-Stable?

This version generates new values based on counts—it doesn't move original elements. If the input contained objects like {value: 2, id: 'A'} and {value: 2, id: 'B'}, we couldn't reconstruct them from just knowing 'there are 2 twos'. Stability requires a different approach.

Cumulative Counts for Position Calculation

To achieve stability (and sort objects with associated data), we need to know not just how many elements have each value, but where elements of each value should be placed in the output. This requires transforming counts into cumulative counts (also called prefix sums).

Key Insight: If count[i] represents how many elements have value i, then the cumulative count tells us: 'After placing all elements with values < i, the next available position is...'

Formally, cumulative count C'[i] = sum of all C[j] for j < i.

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
/**
 * Transform count array into cumulative count array.
 * 
 * After transformation:
 *   C[i] = number of elements with value < i
 *        = starting position for elements with value i
 * 
 * Example:
 *   Count:       [2, 1, 3, 1]  (2 zeros, 1 one, 3 twos, 1 three)
 *   
 *   Cumulative:  [0, 2, 3, 6]
 *                 ↑  ↑  ↑  ↑
 *                 │  │  │  └─ 3s start at index 6 (after 2+1+3=6 elements)
 *                 │  │  └──── 2s start at index 3 (after 2+1=3 elements)
 *                 │  └─────── 1s start at index 2 (after 2 elements)
 *                 └────────── 0s start at index 0 (first)
 */
function computeCumulativeCounts(count: number[]): number[] {
    const cumulative = new Array(count.length);
    
    cumulative[0] = 0;  // First value starts at index 0
    
    for (let i = 1; i < count.length; i++) {
        // Position for value i = position for value (i-1) + count of (i-1)
        cumulative[i] = cumulative[i - 1] + count[i - 1];
    }
    
    return cumulative;
}
 
// Alternative: Cumulative sum that includes current value
// C[i] = number of elements with value ≤ i
// This is useful for right-to-left traversal in stable sort
function computeCumulativeCountsInclusive(count: number[]): number[] {
    const cumulative = [...count];  // Copy original counts
    
    for (let i = 1; i < cumulative.length; i++) {
        cumulative[i] += cumulative[i - 1];
    }
    
    return cumulative;
}
 
// Example
const count = [2, 1, 3, 1];
console.log(computeCumulativeCounts(count));            // [0, 2, 3, 6]
console.log(computeCumulativeCountsInclusive(count));   // [2, 3, 6, 7]

Count vs Cumulative Count Interpretation
Array Type	C[i] Represents	Use Case
Raw Count	Number of elements equal to i	Simple non-stable sort
Cumulative (Exclusive)	Start position for elements with value i	Stable sort (left-to-right)
Cumulative (Inclusive)	End position after placing all elements ≤ i	Stable sort (right-to-left)

Stable Counting Sort Algorithm

The stable version of counting sort uses cumulative counts to place each original element in its correct position, preserving relative order among equal elements. This is the standard counting sort used as a subroutine in radix sort.

The algorithm processes the input right-to-left, and for each element:

Look up its value to find the target position from the cumulative count
Place the element at that position in the output
Decrement the cumulative count (next element with same value goes one position earlier)

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/**
 * Stable Counting Sort: Preserves relative order of equal elements.
 * 
 * This is the standard counting sort algorithm, essential for:
 * - Radix sort (sorting by successive digits)
 * - Sorting objects by a key field
 * - Any situation where duplicate handling matters
 * 
 * Time: O(n + k)
 * Space: O(n + k)
 * Stability: STABLE
 */
function stableCountingSort(arr: number[], k: number): number[] {
    const n = arr.length;
    if (n === 0) return [];
    
    // Phase 1: Build count array - O(n)
    const count = new Array(k).fill(0);
    for (const value of arr) {
        count[value]++;
    }
    
    // Phase 2: Transform to cumulative counts (inclusive) - O(k)
    // After this, count[i] = number of elements ≤ i
    for (let i = 1; i < k; i++) {
        count[i] += count[i - 1];
    }
    
    // Phase 3: Place elements in output array - O(n)
    // Process RIGHT-TO-LEFT for stability
    const output = new Array(n);
    
    for (let i = n - 1; i >= 0; i--) {
        const value = arr[i];
        
        // count[value] gives position AFTER the last element with this value
        // Decrement first to get 0-indexed position
        count[value]--;
        
        // Place element at its correct sorted position
        output[count[value]] = value;
    }
    
    return output;
}
 
// Example demonstrating stability
interface Item { value: number; id: string; }
 
function stableCountingSortObjects(
    arr: Item[], 
    k: number
): Item[] {
    const n = arr.length;
    if (n === 0) return [];
    
    const count = new Array(k).fill(0);
    for (const item of arr) {
        count[item.value]++;
    }
    
    for (let i = 1; i < k; i++) {
        count[i] += count[i - 1];
    }
    
    const output = new Array(n);
    for (let i = n - 1; i >= 0; i--) {
        const item = arr[i];
        count[item.value]--;
        output[count[item.value]] = item;
    }
    
    return output;
}
 
// Stability test
const items: Item[] = [
    { value: 2, id: 'A' },
    { value: 1, id: 'B' },
    { value: 2, id: 'C' },
    { value: 1, id: 'D' }
];
 
const sortedItems = stableCountingSortObjects(items, 3);
console.log(sortedItems);
// [{ value: 1, id: 'B' }, { value: 1, id: 'D' },
//  { value: 2, id: 'A' }, { value: 2, id: 'C' }]
// Note: B before D, A before C - original order preserved!

Why Right-to-Left?

Processing right-to-left with inclusive cumulative counts places equal elements in reverse order of encounter, which restores their original left-to-right order. Processing left-to-right would reverse it. This subtle detail is critical for stability.

Trace Through Stable Counting Sort

Let's trace through the stable counting sort step by step to understand how cumulative counts and right-to-left processing achieve stability.

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
Input: A = [2, 0, 2, 1, 0]
Range k = 3 (values 0, 1, 2)
n = 5
 
════════════════════════════════════════════════════════════
PHASE 1: Build Count Array
════════════════════════════════════════════════════════════
 
count = [0, 0, 0]  (initialized)
 
Process each element:
  A[0] = 2: count[2]++ → count = [0, 0, 1]
  A[1] = 0: count[0]++ → count = [1, 0, 1]
  A[2] = 2: count[2]++ → count = [1, 0, 2]
  A[3] = 1: count[1]++ → count = [1, 1, 2]
  A[4] = 0: count[0]++ → count = [2, 1, 2]
 
Final count: [2, 1, 2]
  → 2 zeros, 1 one, 2 twos
 
════════════════════════════════════════════════════════════
PHASE 2: Cumulative Sum (Inclusive)
════════════════════════════════════════════════════════════
 
cumulative[0] = count[0] = 2
cumulative[1] = cumulative[0] + count[1] = 2 + 1 = 3
cumulative[2] = cumulative[1] + count[2] = 3 + 2 = 5
 
Cumulative count: [2, 3, 5]
 
Interpretation:
  count[0] = 2: There are 2 elements with value ≤ 0
                So 0s fill positions 0-1 (indices 0 and 1)
  count[1] = 3: There are 3 elements with value ≤ 1
                So 1s fill position 2
  count[2] = 5: There are 5 elements with value ≤ 2
                So 2s fill positions 3-4
 
════════════════════════════════════════════════════════════
PHASE 3: Place Elements (Right-to-Left)
════════════════════════════════════════════════════════════
 
output = [_, _, _, _, _]
count  = [2, 3, 5]
 
Step 1: i = 4, A[4] = 0
        count[0]-- → count[0] = 1
        output[1] = 0
        output = [_, 0, _, _, _]
        count  = [1, 3, 5]
 
Step 2: i = 3, A[3] = 1
        count[1]-- → count[1] = 2
        output[2] = 1
        output = [_, 0, 1, _, _]
        count  = [1, 2, 5]
 
Step 3: i = 2, A[2] = 2
        count[2]-- → count[2] = 4
        output[4] = 2
        output = [_, 0, 1, _, 2]
        count  = [1, 2, 4]
 
Step 4: i = 1, A[1] = 0
        count[0]-- → count[0] = 0
        output[0] = 0
        output = [0, 0, 1, _, 2]
        count  = [0, 2, 4]
 
Step 5: i = 0, A[0] = 2
        count[2]-- → count[2] = 3
        output[3] = 2
        output = [0, 0, 1, 2, 2]
        count  = [0, 2, 3]
 
═══════════════════════════════════════════════════════════
FINAL OUTPUT: [0, 0, 1, 2, 2] ✓
═══════════════════════════════════════════════════════════
 
Stability Verification:
  Original 2s: A[0]=2 was at index 0, A[2]=2 was at index 2
  Sorted 2s:   First 2 at index 3, Second 2 at index 4
  
  A[0] (first 2 in input) → output[3] (first 2 in output) ✓
  A[2] (second 2 in input) → output[4] (second 2 in output) ✓
  
  Order preserved! That's stability.

Why Stability Matters

Stability might seem like a minor technical detail, but it has profound practical implications. Without stability, counting sort couldn't serve as the building block for radix sort, one of the most powerful sorting algorithms for fixed-width integers and strings.

Critical Use Cases for Stability

•Radix Sort: Sorts by each digit from least significant to most significant. Stability ensures earlier digit orderings are preserved when sorting by later digits. Without stability, radix sort breaks completely.
•Multi-Key Sorting: Sort records first by secondary key, then by primary key. Stability ensures secondary order is maintained within primary groups. Example: sort employees by department, then by salary within department.
•Sorting Objects: When sorting by one field of a complex object, you often want to preserve the order established by previous operations. Databases rely on this for compound sorting.
•Deterministic Output: For equal elements, stable sort produces consistent output. Unstable sorts may produce different orderings across runs, complicating testing and debugging.

Radix Sort Depends on Stability

Radix sort sorts integers digit-by-digit, least significant first. After sorting by the ones digit, tens digit sorting must not disturb the ones ordering within equal tens values. Only a stable sort preserves this. Using an unstable counting sort makes radix sort produce wrong results.

In-Place Considerations

Standard counting sort requires O(n) auxiliary space for the output array. Can we sort in-place? The answer is nuanced:

For bare integers (simple version): Yes, we can write directly back to the input array:

function inPlaceSimpleCountingSort(arr: number[], k: number): void {
    const count = new Array(k).fill(0);
    for (const v of arr) count[v]++;
    
    let idx = 0;
    for (let v = 0; v < k; v++) {
        for (let i = 0; i < count[v]; i++) {
            arr[idx++] = v;
        }
    }
}

For stable sorting: There is no simple in-place stable counting sort. The output array is necessary to place elements while reading from the input. Some complex cycle-sort-based approaches exist but are impractical.

Practical reality: The O(n) output space is rarely a problem. If sorting n elements, you already have O(n) input space. Doubling memory for sorting is acceptable in most contexts.

Counting Sort Space Variants
Variant	Count Array	Output Array	Total Space	Stable?
Simple Counting Sort	O(k)	O(n)	O(n + k)	No
In-Place Simple	O(k)	O(1)*	O(k)	No
Stable Counting Sort	O(k)	O(n)	O(n + k)	Yes

Trade-off Summary

In-place simple counting sort overwrites the input, which is technically 'in-place' but destroys original information. For objects, you'd need O(n) anyway to preserve the original data. In practice, just allocate the output array.

Common Implementation Pitfalls

Counting sort's simplicity is deceptive. These bugs appear frequently in implementations:

Critical Bugs to Avoid

•Off-by-one in range: If values range from 1 to k (not 0 to k-1), you need a count array of size k+1, or offset all values by -1.
•Wrong traversal direction: Left-to-right placement loses stability. Always process right-to-left for stable sorting.
•Forgetting to decrement count: After placing an element, decrement the cumulative count so the next equal element goes to a different (earlier) position.
•Type coercion issues: In JavaScript/TypeScript, ensure values are integers. count[3.5] creates havoc (array with floating-point keys).
•Negative values without offset: If values can be negative, normalize first. count[-5] doesn't work as expected in most languages.
•Modifying cumulative array prematurely: If you need the original counts later (e.g., for verification), copy before transforming to cumulative.

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
function robustCountingSort(arr: number[]): number[] {
    if (arr.length === 0) return [];
    
    // Handle arbitrary integer ranges
    const min = Math.min(...arr);
    const max = Math.max(...arr);
    const k = max - min + 1;
    
    // Validate input (optional but recommended)
    for (const v of arr) {
        if (!Number.isInteger(v)) {
            throw new Error(`Non-integer value: ${v}`);
        }
    }
    
    // Count with offset normalization
    const count = new Array(k).fill(0);
    for (const v of arr) {
        count[v - min]++;  // Shift by min
    }
    
    // Cumulative sum
    for (let i = 1; i < k; i++) {
        count[i] += count[i - 1];
    }
    
    // Stable placement (right-to-left)
    const output = new Array(arr.length);
    for (let i = arr.length - 1; i >= 0; i--) {
        const normalizedValue = arr[i] - min;
        count[normalizedValue]--;
        output[count[normalizedValue]] = arr[i];  // Denormalize in output
    }
    
    return output;
}

Summary: The Power of Counting

The counting phase is the heart of counting sort. By tallying occurrences and computing cumulative positions, we transform the sorting problem into a direct addressing problem.

Key Takeaways

•The count array tallies occurrences: C[i] = number of elements with value i. Built in O(n) time.
•Cumulative counts reveal positions: Transform counts to know where each value group belongs in sorted output.
•Simple counting sort reconstructs by value: Fast and easy, but not stable. Use for bare integers only.
•Stable counting sort places original elements: Uses cumulative counts and right-to-left traversal. Essential for radix sort and object sorting.
•Stability requires right-to-left processing: This counter-intuitive detail preserves original order among equal elements.
•Watch for implementation pitfalls: Off-by-one errors, wrong traversal direction, and negative number handling are common traps.

Page Complete

You now understand the counting mechanism that powers counting sort. The count array captures the frequency distribution; cumulative counts encode position information; right-to-left placement ensures stability. Next, we'll analyze the precise time complexity O(n + k) and understand what each term contributes.

2 / 4

Loading learning content...

Data Structures & AlgorithmsCounting Sort — Non-Comparison Sorting

Counting Sort: Breaking the Comparison-Based Barrier

LevelIntermediate

Duration55 mins

TopicCounting Sort — Non-Comparison Sorting

2 / 4

Counting Occurrences

The Heart of the Algorithm

The Counting Insight

The Count Array Concept

Definition: Given input array A of n elements with values in [0, k-1], the count array C of size k satisfies:

C[i] = |{j : A[j] = i}|

In words: C[i] equals the count of elements in A that equal i.

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
/**
 * Build a count array from input values.
 * 
 * Example:
 *   Input: [2, 0, 2, 3, 1, 0, 2]
 *   Range: 0 to 3 (k = 4)
 *   
 *   Count Array:
 *     Index 0: count of 0s → 2
 *     Index 1: count of 1s → 1
 *     Index 2: count of 2s → 3
 *     Index 3: count of 3s → 1
 *     
 *   C = [2, 1, 3, 1]
 */
function buildCountArray(arr: number[], k: number): number[] {
    // Initialize count array with zeros
    const count = new Array(k).fill(0);
    
    // Single pass through input: O(n)
    for (const value of arr) {
        count[value]++;  // Direct addressing: value IS the index
    }
    
    return count;
}
 
// Example execution
const input = [2, 0, 2, 3, 1, 0, 2];
const k = 4;  // Values range from 0 to 3
const counts = buildCountArray(input, k);
console.log(counts);  // [2, 1, 3, 1]
 
// Verify: sum of counts equals array length
console.log(counts.reduce((a, b) => a + b));  // 7 (correct!)

Direct Addressing in Action

Visualizing the Counting Process

Let's trace through the counting process step by step to build intuition.

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
Input Array: [2, 0, 2, 3, 1, 0, 2]
Range k = 4 (values 0, 1, 2, 3)
 
Initial Count Array: [0, 0, 0, 0]
                      ↑  ↑  ↑  ↑
                      0  1  2  3
 
Step 1: Process A[0] = 2
        count[2]++
        Count: [0, 0, 1, 0]     ← One 2 seen
 
Step 2: Process A[1] = 0
        count[0]++
        Count: [1, 0, 1, 0]     ← One 0 seen
 
Step 3: Process A[2] = 2
        count[2]++
        Count: [1, 0, 2, 0]     ← Two 2s seen
 
Step 4: Process A[3] = 3
        count[3]++
        Count: [1, 0, 2, 1]     ← One 3 seen
 
Step 5: Process A[4] = 1
        count[1]++
        Count: [1, 1, 2, 1]     ← One 1 seen
 
Step 6: Process A[5] = 0
        count[0]++
        Count: [2, 1, 2, 1]     ← Two 0s seen
 
Step 7: Process A[6] = 2
        count[2]++
        Count: [2, 1, 3, 1]     ← Three 2s seen
 
Final Count Array: [2, 1, 3, 1]
 
Interpretation:
  • 2 elements have value 0
  • 1 element has value 1
  • 3 elements have value 2
  • 1 element has value 3
 
Sorted output (by reading counts): [0, 0, 1, 2, 2, 2, 3]

One Pass, Complete Information

After a single O(n) pass, we know exactly how many of each value exist. This information is sufficient to produce sorted output—we've essentially 'sorted' the data by categorizing it.

Simple Counting Sort (Non-Stable Version)

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
/**
 * Simple Counting Sort: Sort integers using count-based reconstruction.
 * 
 * Algorithm:
 * 1. Build count array: count[i] = number of elements equal to i
 * 2. Reconstruct: output count[i] copies of value i, for each i
 * 
 * Time: O(n + k)
 * Space: O(k) for count array + O(n) for output = O(n + k)
 * Stability: NOT STABLE
 */
function simpleCountingSort(arr: number[], k: number): number[] {
    if (arr.length === 0) return [];
    
    // Phase 1: Build count array - O(k) init + O(n) counting
    const count = new Array(k).fill(0);
    for (const value of arr) {
        count[value]++;
    }
    
    // Phase 2: Reconstruct sorted output - O(n + k)
    const output: number[] = [];
    for (let value = 0; value < k; value++) {
        // Add 'count[value]' copies of 'value' to output
        for (let i = 0; i < count[value]; i++) {
            output.push(value);
        }
    }
    
    return output;
}
 
// Example usage
const unsorted = [4, 2, 2, 8, 3, 3, 1];
const k = 9;  // Values range 0-8
const sorted = simpleCountingSort(unsorted, k);
console.log(sorted);  // [1, 2, 2, 3, 3, 4, 8]

Why Non-Stable?

Cumulative Counts for Position Calculation

Key Insight: If count[i] represents how many elements have value i, then the cumulative count tells us: 'After placing all elements with values < i, the next available position is...'

Formally, cumulative count C'[i] = sum of all C[j] for j < i.

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
/**
 * Transform count array into cumulative count array.
 * 
 * After transformation:
 *   C[i] = number of elements with value < i
 *        = starting position for elements with value i
 * 
 * Example:
 *   Count:       [2, 1, 3, 1]  (2 zeros, 1 one, 3 twos, 1 three)
 *   
 *   Cumulative:  [0, 2, 3, 6]
 *                 ↑  ↑  ↑  ↑
 *                 │  │  │  └─ 3s start at index 6 (after 2+1+3=6 elements)
 *                 │  │  └──── 2s start at index 3 (after 2+1=3 elements)
 *                 │  └─────── 1s start at index 2 (after 2 elements)
 *                 └────────── 0s start at index 0 (first)
 */
function computeCumulativeCounts(count: number[]): number[] {
    const cumulative = new Array(count.length);
    
    cumulative[0] = 0;  // First value starts at index 0
    
    for (let i = 1; i < count.length; i++) {
        // Position for value i = position for value (i-1) + count of (i-1)
        cumulative[i] = cumulative[i - 1] + count[i - 1];
    }
    
    return cumulative;
}
 
// Alternative: Cumulative sum that includes current value
// C[i] = number of elements with value ≤ i
// This is useful for right-to-left traversal in stable sort
function computeCumulativeCountsInclusive(count: number[]): number[] {
    const cumulative = [...count];  // Copy original counts
    
    for (let i = 1; i < cumulative.length; i++) {
        cumulative[i] += cumulative[i - 1];
    }
    
    return cumulative;
}
 
// Example
const count = [2, 1, 3, 1];
console.log(computeCumulativeCounts(count));            // [0, 2, 3, 6]
console.log(computeCumulativeCountsInclusive(count));   // [2, 3, 6, 7]

Count vs Cumulative Count Interpretation
Array Type	C[i] Represents	Use Case
Raw Count	Number of elements equal to i	Simple non-stable sort
Cumulative (Exclusive)	Start position for elements with value i	Stable sort (left-to-right)
Cumulative (Inclusive)	End position after placing all elements ≤ i	Stable sort (right-to-left)

Stable Counting Sort Algorithm

The algorithm processes the input right-to-left, and for each element:

Look up its value to find the target position from the cumulative count
Place the element at that position in the output
Decrement the cumulative count (next element with same value goes one position earlier)

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/**
 * Stable Counting Sort: Preserves relative order of equal elements.
 * 
 * This is the standard counting sort algorithm, essential for:
 * - Radix sort (sorting by successive digits)
 * - Sorting objects by a key field
 * - Any situation where duplicate handling matters
 * 
 * Time: O(n + k)
 * Space: O(n + k)
 * Stability: STABLE
 */
function stableCountingSort(arr: number[], k: number): number[] {
    const n = arr.length;
    if (n === 0) return [];
    
    // Phase 1: Build count array - O(n)
    const count = new Array(k).fill(0);
    for (const value of arr) {
        count[value]++;
    }
    
    // Phase 2: Transform to cumulative counts (inclusive) - O(k)
    // After this, count[i] = number of elements ≤ i
    for (let i = 1; i < k; i++) {
        count[i] += count[i - 1];
    }
    
    // Phase 3: Place elements in output array - O(n)
    // Process RIGHT-TO-LEFT for stability
    const output = new Array(n);
    
    for (let i = n - 1; i >= 0; i--) {
        const value = arr[i];
        
        // count[value] gives position AFTER the last element with this value
        // Decrement first to get 0-indexed position
        count[value]--;
        
        // Place element at its correct sorted position
        output[count[value]] = value;
    }
    
    return output;
}
 
// Example demonstrating stability
interface Item { value: number; id: string; }
 
function stableCountingSortObjects(
    arr: Item[], 
    k: number
): Item[] {
    const n = arr.length;
    if (n === 0) return [];
    
    const count = new Array(k).fill(0);
    for (const item of arr) {
        count[item.value]++;
    }
    
    for (let i = 1; i < k; i++) {
        count[i] += count[i - 1];
    }
    
    const output = new Array(n);
    for (let i = n - 1; i >= 0; i--) {
        const item = arr[i];
        count[item.value]--;
        output[count[item.value]] = item;
    }
    
    return output;
}
 
// Stability test
const items: Item[] = [
    { value: 2, id: 'A' },
    { value: 1, id: 'B' },
    { value: 2, id: 'C' },
    { value: 1, id: 'D' }
];
 
const sortedItems = stableCountingSortObjects(items, 3);
console.log(sortedItems);
// [{ value: 1, id: 'B' }, { value: 1, id: 'D' },
//  { value: 2, id: 'A' }, { value: 2, id: 'C' }]
// Note: B before D, A before C - original order preserved!

Why Right-to-Left?

Trace Through Stable Counting Sort

Let's trace through the stable counting sort step by step to understand how cumulative counts and right-to-left processing achieve stability.

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
Input: A = [2, 0, 2, 1, 0]
Range k = 3 (values 0, 1, 2)
n = 5
 
════════════════════════════════════════════════════════════
PHASE 1: Build Count Array
════════════════════════════════════════════════════════════
 
count = [0, 0, 0]  (initialized)
 
Process each element:
  A[0] = 2: count[2]++ → count = [0, 0, 1]
  A[1] = 0: count[0]++ → count = [1, 0, 1]
  A[2] = 2: count[2]++ → count = [1, 0, 2]
  A[3] = 1: count[1]++ → count = [1, 1, 2]
  A[4] = 0: count[0]++ → count = [2, 1, 2]
 
Final count: [2, 1, 2]
  → 2 zeros, 1 one, 2 twos
 
════════════════════════════════════════════════════════════
PHASE 2: Cumulative Sum (Inclusive)
════════════════════════════════════════════════════════════
 
cumulative[0] = count[0] = 2
cumulative[1] = cumulative[0] + count[1] = 2 + 1 = 3
cumulative[2] = cumulative[1] + count[2] = 3 + 2 = 5
 
Cumulative count: [2, 3, 5]
 
Interpretation:
  count[0] = 2: There are 2 elements with value ≤ 0
                So 0s fill positions 0-1 (indices 0 and 1)
  count[1] = 3: There are 3 elements with value ≤ 1
                So 1s fill position 2
  count[2] = 5: There are 5 elements with value ≤ 2
                So 2s fill positions 3-4
 
════════════════════════════════════════════════════════════
PHASE 3: Place Elements (Right-to-Left)
════════════════════════════════════════════════════════════
 
output = [_, _, _, _, _]
count  = [2, 3, 5]
 
Step 1: i = 4, A[4] = 0
        count[0]-- → count[0] = 1
        output[1] = 0
        output = [_, 0, _, _, _]
        count  = [1, 3, 5]
 
Step 2: i = 3, A[3] = 1
        count[1]-- → count[1] = 2
        output[2] = 1
        output = [_, 0, 1, _, _]
        count  = [1, 2, 5]
 
Step 3: i = 2, A[2] = 2
        count[2]-- → count[2] = 4
        output[4] = 2
        output = [_, 0, 1, _, 2]
        count  = [1, 2, 4]
 
Step 4: i = 1, A[1] = 0
        count[0]-- → count[0] = 0
        output[0] = 0
        output = [0, 0, 1, _, 2]
        count  = [0, 2, 4]
 
Step 5: i = 0, A[0] = 2
        count[2]-- → count[2] = 3
        output[3] = 2
        output = [0, 0, 1, 2, 2]
        count  = [0, 2, 3]
 
═══════════════════════════════════════════════════════════
FINAL OUTPUT: [0, 0, 1, 2, 2] ✓
═══════════════════════════════════════════════════════════
 
Stability Verification:
  Original 2s: A[0]=2 was at index 0, A[2]=2 was at index 2
  Sorted 2s:   First 2 at index 3, Second 2 at index 4
  
  A[0] (first 2 in input) → output[3] (first 2 in output) ✓
  A[2] (second 2 in input) → output[4] (second 2 in output) ✓
  
  Order preserved! That's stability.

Why Stability Matters

Critical Use Cases for Stability

•Radix Sort: Sorts by each digit from least significant to most significant. Stability ensures earlier digit orderings are preserved when sorting by later digits. Without stability, radix sort breaks completely.
•Multi-Key Sorting: Sort records first by secondary key, then by primary key. Stability ensures secondary order is maintained within primary groups. Example: sort employees by department, then by salary within department.
•Sorting Objects: When sorting by one field of a complex object, you often want to preserve the order established by previous operations. Databases rely on this for compound sorting.
•Deterministic Output: For equal elements, stable sort produces consistent output. Unstable sorts may produce different orderings across runs, complicating testing and debugging.

Radix Sort Depends on Stability

In-Place Considerations

Standard counting sort requires O(n) auxiliary space for the output array. Can we sort in-place? The answer is nuanced:

For bare integers (simple version): Yes, we can write directly back to the input array:

function inPlaceSimpleCountingSort(arr: number[], k: number): void {
    const count = new Array(k).fill(0);
    for (const v of arr) count[v]++;
    
    let idx = 0;
    for (let v = 0; v < k; v++) {
        for (let i = 0; i < count[v]; i++) {
            arr[idx++] = v;
        }
    }
}

Practical reality: The O(n) output space is rarely a problem. If sorting n elements, you already have O(n) input space. Doubling memory for sorting is acceptable in most contexts.

Counting Sort Space Variants
Variant	Count Array	Output Array	Total Space	Stable?
Simple Counting Sort	O(k)	O(n)	O(n + k)	No
In-Place Simple	O(k)	O(1)*	O(k)	No
Stable Counting Sort	O(k)	O(n)	O(n + k)	Yes

Trade-off Summary

In-place simple counting sort overwrites the input, which is technically 'in-place' but destroys original information. For objects, you'd need O(n) anyway to preserve the original data. In practice, just allocate the output array.

Common Implementation Pitfalls

Counting sort's simplicity is deceptive. These bugs appear frequently in implementations:

Critical Bugs to Avoid

•Off-by-one in range: If values range from 1 to k (not 0 to k-1), you need a count array of size k+1, or offset all values by -1.
•Wrong traversal direction: Left-to-right placement loses stability. Always process right-to-left for stable sorting.
•Forgetting to decrement count: After placing an element, decrement the cumulative count so the next equal element goes to a different (earlier) position.
•Type coercion issues: In JavaScript/TypeScript, ensure values are integers. count[3.5] creates havoc (array with floating-point keys).
•Negative values without offset: If values can be negative, normalize first. count[-5] doesn't work as expected in most languages.
•Modifying cumulative array prematurely: If you need the original counts later (e.g., for verification), copy before transforming to cumulative.

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
function robustCountingSort(arr: number[]): number[] {
    if (arr.length === 0) return [];
    
    // Handle arbitrary integer ranges
    const min = Math.min(...arr);
    const max = Math.max(...arr);
    const k = max - min + 1;
    
    // Validate input (optional but recommended)
    for (const v of arr) {
        if (!Number.isInteger(v)) {
            throw new Error(`Non-integer value: ${v}`);
        }
    }
    
    // Count with offset normalization
    const count = new Array(k).fill(0);
    for (const v of arr) {
        count[v - min]++;  // Shift by min
    }
    
    // Cumulative sum
    for (let i = 1; i < k; i++) {
        count[i] += count[i - 1];
    }
    
    // Stable placement (right-to-left)
    const output = new Array(arr.length);
    for (let i = arr.length - 1; i >= 0; i--) {
        const normalizedValue = arr[i] - min;
        count[normalizedValue]--;
        output[count[normalizedValue]] = arr[i];  // Denormalize in output
    }
    
    return output;
}

Summary: The Power of Counting

The counting phase is the heart of counting sort. By tallying occurrences and computing cumulative positions, we transform the sorting problem into a direct addressing problem.

Key Takeaways

•The count array tallies occurrences: C[i] = number of elements with value i. Built in O(n) time.
•Cumulative counts reveal positions: Transform counts to know where each value group belongs in sorted output.
•Simple counting sort reconstructs by value: Fast and easy, but not stable. Use for bare integers only.
•Stable counting sort places original elements: Uses cumulative counts and right-to-left traversal. Essential for radix sort and object sorting.
•Stability requires right-to-left processing: This counter-intuitive detail preserves original order among equal elements.
•Watch for implementation pitfalls: Off-by-one errors, wrong traversal direction, and negative number handling are common traps.

Page Complete

2 / 4