Counting Sort Algorithm in DSA Javascript

Mental Model

Counting sort counts how many times each number appears, then uses these counts to place numbers in order without comparing them.

Analogy: Imagine sorting colored balls by putting them into labeled boxes for each color, then taking them out in order to get a sorted line of balls.

Input array: [4, 2, 2, 8, 3, 3, 1]
Count array: [0, 1, 2, 2, 1, 0, 0, 0, 1]
Sorted output: []

Dry Run Walkthrough

Input: array: [4, 2, 2, 8, 3, 3, 1]

Goal: Sort the array in ascending order using counting sort

Step 1: Count how many times each number appears

Count array: [0, 1, 2, 2, 1, 0, 0, 0, 1]

Why: We need to know the frequency of each number to place them correctly

Step 2: Change counts to cumulative counts

Count array: [0, 1, 3, 5, 6, 6, 6, 6, 7]

Why: Cumulative counts tell us the position where each number should go

Step 3: Place numbers into output array from right to left using cumulative counts

Output array after placing all: [1, 2, 2, 3, 3, 4, 8]

Why: Placing from right to left keeps the sort stable and uses counts to find positions

Result:

Sorted array: [1, 2, 2, 3, 3, 4, 8]

Annotated Code

DSA Javascript

class CountingSort {
  static sort(arr) {
    if (arr.length === 0) return arr;

    // Find max value to size count array
    const max = Math.max(...arr);
    const count = new Array(max + 1).fill(0);

    // Count occurrences
    for (const num of arr) {
      count[num]++;
    }

    // Change count to cumulative count
    for (let i = 1; i < count.length; i++) {
      count[i] += count[i - 1];
    }

    const output = new Array(arr.length);

    // Place elements in output array from right to left
    for (let i = arr.length - 1; i >= 0; i--) {
      const num = arr[i];
      count[num]--;
      output[count[num]] = num;
    }

    return output;
  }
}

// Driver code
const input = [4, 2, 2, 8, 3, 3, 1];
const sorted = CountingSort.sort(input);
console.log(sorted.join(", ") + "\n");

const max = Math.max(...arr);

Find the largest number to know count array size

for (const num of arr) { count[num]++; }

Count how many times each number appears

for (let i = 1; i < count.length; i++) { count[i] += count[i - 1]; }

Convert counts to cumulative counts for positions

for (let i = arr.length - 1; i >= 0; i--) { count[num]--; output[count[num]] = num; }

Place elements in output array from right to left using counts

Output

1, 2, 2, 3, 3, 4, 8

Complexity Analysis

Time: O(n + k) because we count frequencies and then place elements, where n is array length and k is max value

Space: O(n + k) because we use output array of size n and count array of size k+1

vs Alternative: Unlike comparison sorts (O(n log n)), counting sort is faster for small ranges but uses extra space

Edge Cases

empty array

returns empty array immediately

DSA Javascript

if (arr.length === 0) return arr;

array with one element

returns array as is

DSA Javascript

handles naturally without special code

array with all same elements

returns array unchanged but sorted

DSA Javascript

counting and placement still works correctly

When to Use This Pattern

When you need to sort integers with a small range quickly and without comparisons, use counting sort because it counts frequencies and places elements directly.

Common Mistakes

Mistake: Not converting counts to cumulative counts before placement
Fix: Add loop to convert counts to cumulative counts before placing elements

Mistake: Placing elements from left to right causing unstable sort
Fix: Place elements from right to left to maintain stability

Summary

Counting sort sorts numbers by counting their occurrences and using these counts to place them in order.

Use it when sorting integers with a limited range for fast, non-comparison sorting.

The key insight is converting counts to cumulative counts to find exact positions for each number.