A Voyage through Algorithms using Javascript - Counting Sort

What is Counting Sort?

Counting Sort is a specialized non-comparison based sorting algorithm that works by counting how many times each number appears in the array, then using those occurrence counts to rebuild the sorted result. Unlike the comparison-based algorithms we've explored like Bubble Sort, Insertion Sort, and Merge Sort, Counting Sort doesn't compare numbers to each other at all. Instead, it leverages the simple concept of counting occurrences to achieve O(n + k) time complexity, where n is the number of elements and k is the range of input values.

The core logic is straightforward: if you know you have three 5's, two 8's, and one 1, you can rebuild the sorted array [1, 5, 5, 5, 8, 8] without ever comparing individual numbers.

Counting Sort is a niche algorithm that shines in specific scenarios: particularly when sorting integers within a known, limited range. It's not a general-purpose sorting solution like comparison-based ones, but when the conditions are right, it can outperform even the most optimized comparison-based sorts. Especially when you're working with integers in a relatively small range.

How Counting Sort Works

Counting Sort operates through four straightforward steps:

1. Find the range: Determine the smallest and largest numbers in the array so we know what values we're working with.
2. Create counting buckets: Set up a count array where each index represents a possible value in our range.
3. Count occurrences: Go through the input array and count how many times each number appears.
4. Rebuild the sorted array: Use the occurrence counts to construct the final result by adding each number the correct number of times.

The process is simple: instead of asking "is this number bigger than that number?", Counting Sort just asks "how many times does each number appear?" Once you have those counts, rebuilding the sorted array is straightforward.

Here's a visualization to make the concept clearer:

Implementing Counting Sort in JavaScript

Let's take a look at the implementation of Counting Sort in JavaScript, with detailed comments explaining each part:

function countingSort(arr) {
  if (arr.length === 0) return arr;

  // STEP 1: Find the range of numbers we're working with
  // We need to know the smallest and biggest numbers to figure out
  // how many counting buckets we need and how to map values to bucket indices
  let minOffset = arr[0];
  let maxOffset = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < minOffset) minOffset = arr[i];
    if (arr[i] > maxOffset) maxOffset = arr[i];
  }

  // STEP 2: Create our counting buckets
  // We need one bucket for each possible value in our range
  // Example: If the values range from 11 to 15, we need 5 buckets (15 - 11 + 1 = 5)
  const range = maxOffset - minOffset + 1;
  const count = new Array(range);  // Sparse array - undefined slots are okay

  // STEP 3: Count how many times each number appears
  // The trick: map each value to a bucket index by subtracting minOffset
  for (let i = 0; i < arr.length; i++) {
    let value = arr[i];
    // Map value to bucket index: value 11 becomes index 0, value 12 becomes index 1, etc.
    let bucketIndex = value - minOffset;  
    let occurrences = count[bucketIndex] || 0;  // Handle undefined as 0
    count[bucketIndex] = occurrences + 1;  // Increment the count for this bucket
  }

  // STEP 4: Rebuild the sorted array by going through each bucket in order
  // For each bucket that has a count, add that original value to result
  const result = [];
  for (let i = 0; i < count.length; i++) {
    if (count[i]) {  // Skip buckets that are empty (undefined)
      // Convert bucket index back to original value: index 0 becomes value 11, etc.
      let originalValue = i + minOffset;  
      // Add this value to result as many times as we counted it
      while (count[i] > 0) {
        result.push(originalValue);
        count[i]--;  // Decrease count until we've added all occurrences
      }
    }
  }

  return result;
}

Key Implementation Details for Counting Sort

1. The Range Calculation Magic

const range = maxOffset - minOffset + 1;

We need exactly one bucket for each possible value. If our numbers go from 11 to 15, that's 5 different values (11, 12, 13, 14, 15), so we need 5 buckets.

2. The Compression Trick: value - minOffset

let bucketIndex = value - minOffset;  // Maps 11→0, 12→1, 13→2, etc.

Array indices must start at 0, but our values might start anywhere. Subtracting minOffset "compresses" any range of values to fit bucket indices starting at 0.

3. Sparse Arrays Are Your Friend

// Creates an array based on range with undefined slots
const count = new Array(range);
// ...
let occurrences = count[bucketIndex] || 0;  // Treats undefined as 0

No need to fill with zeros! We handle undefined values gracefully, which saves time when dealing with sparse data.

4. The Expansion Trick: i + minOffset

let originalValue = i + minOffset;  // Maps 0→11, 1→12, 2→13, etc.

When rebuilding, we "expand" bucket indices back to original values by adding minOffset. This is the reverse of our compression step.

5. Handling Negative Numbers

The offset approach works for any range. With values [-5, -3, -1]:

• minOffset = -5
• Value -5 maps to bucket (-5) - (-5) = 0
• Bucket 0 maps back to 0 + (-5) = -5

The beauty is in the symmetry: compress with subtraction, expand with addition.

Is Counting Sort Stable?

Counting sort is a stable algorithm. However though, the simplified implementation above is not technically stable but practically is, here's why:

Stability means that equal elements maintain their relative order from the original array. Above implementation doesn't preserve this because we simply add each integer value multiple times:

while (count[i] > 0) {
  result.push(originalValue);  // Adds the same value multiple times
  count[i]--;
}

Here's the practical part: when sorting primitive integers like [5, 3, 5, 1, 5], all the 5's are literally identical. There's no way to tell which 5 was "first" or "second" because they're exactly the same value.

Stability only matters when sorting objects where equal comparison values have other distinguishing properties:

// A stable sort would always keep Alice before Charlie
// when sorting by grade alone:
let students = [
  {id: 2, name: "Alice", grade: 85, submitted: '09:52'},
  {id: 4, name: "Charlie", grade: 85, submitted: '10:02'},
  // ...
];

For the integer only use cases, the simple variant above is perfectly suitable. I'll be also including a variant that is both stable and accepts an array of objects at the end of this article.

Time and Space Complexity Analysis

Counting Sort's performance characteristics are:

Time Complexity: O(n + k) in all cases

• n = number of elements in input array
• k = range of input values (maxOffset - minOffset + 1)
• We scan the input once (O(n)) + scan the count array once (O(k))

Space Complexity:

• Where k is for the count array and n for the output array
• Auxiliary space: O(k) - for the count array
• Total space: O(n + k) - including the output array

Smaller k factor = better performance: Counting Sort is only efficient when k is not much larger than n. If you're sorting 10 numbers but they range from 1 to 1,000,000, you'd create a million-element count array for just 10 values. That'd be very wasteful!

This is why Counting Sort shines with small, dense ranges but struggles with sparse data like random large integers.

When to Choose Counting Sort

Counting Sort excels in specific scenarios but has clear limitations. Here's when to consider and when to avoid it:

Perfect for:

• Small integer ranges: Exam grades (0-100), dice rolls (1-6), RGB values (0-255)
• Objects with integer keys: Student records sorted by grade, events by timestamp, inventory by category ID
• Dense data: When most values in your range actually appear in the data
• Performance-critical sorting: Linear O(n + k) time beats any comparison-based sort
• Stable sorting needs: When relative order of equal elements matters

Avoid when:

• Sparse data: Sorting small amounts of numbers with large ranges wastes massive memory
• Unknown ranges: You need to know min/max values beforehand
• Non-integer keys: Floating-point numbers, strings, or objects without suitable integer properties
• Memory constraints: The range (k) creates the space bottleneck

The golden rule: Counting Sort is brilliant when range ≈ array size, terrible when range >> array size.

// Inefficient: sorting 10 numbers from 1 to 1,000,000
// Creates a count array of 1 million elements for just 10 values!
const badExample = [5, 999999, 1, 500000, 10];

Counting sort works with any data as long as the sorting key is an integer in a manageable range.

Real-World Applications

Counting Sort shines in problems where the range of values is known and limited:

Digital Systems: Sorting pixel intensities (0-255), character frequencies in text analysis, network packet priorities

Data Processing: Database indexing with categorical values, sorting by age groups or rating scales, organizing inventory by product categories

Algorithm Building Blocks: Used internally by Radix Sort for sorting individual digits, stable sorting subroutine in hybrid algorithms.

Counting Sort Implementation (Object based variant)

function countingSortObjects(arr, key) {
  if (arr.length === 0) return arr;

  // STEP 1: Find range of the target key values
  let minOffset = arr[0][key];
  let maxOffset = arr[0][key];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i][key] < minOffset) minOffset = arr[i][key];
    if (arr[i][key] > maxOffset) maxOffset = arr[i][key];
  }

  // STEP 2: Count frequencies of the key values
  const range = maxOffset - minOffset + 1;
  const count = new Array(range).fill(0);

  for (let i = 0; i < arr.length; i++) {
    count[arr[i][key] - minOffset]++;
  }

  // STEP 3: Transform to cumulative positions
  // This tells us where each key value should END in the final array
  for (let i = 1; i < count.length; i++) {
    count[i] += count[i - 1];
  }

  // STEP 4: Place objects in their final positions (preserving stability)
  const result = new Array(arr.length);

  // Process backwards to maintain original order of objects with same key value
  for (let i = arr.length - 1; i >= 0; i--) {
    let obj = arr[i];
    let keyValue = obj[key];
    let position = count[keyValue - minOffset] - 1;
    result[position] = obj;  // Place the entire object
    count[keyValue - minOffset]--;
  }

  return result;
}

// Example usage:
const students = [
  {id: 1, name: "Bob", grade: 92, submitted: '09:45'}, 
  {id: 2, name: "Alice", grade: 85, submitted: '09:52'},
  {id: 3, name: "Diana", grade: 78, submitted: '09:58'},
  {id: 4, name: "Charlie", grade: 85, submitted: '10:02'},
];

// Sort by grade - Alice stays before Charlie (both grade 85)
const sortedByGrade = countingSortObjects(students, 'grade');
console.log(sortedByGrade);


/*
Output:

[
  { id: 3, name: 'Diana', grade: 78, submitted: '09:58' },
  { id: 2, name: 'Alice', grade: 85, submitted: '09:52' },
  { id: 4, name: 'Charlie', grade: 85, submitted: '10:02' },
  { id: 1, name: 'Bob', grade: 92, submitted: '09:45' }
]

-----

Notice Alice comes before Charlie - that's stability!

*/

Why stability matters here:

• Alice and Charlie both have grade 85
• A stable sort preserves their original relative order
• Alice was first in the input, so she stays first among the 85s in the output

When to use each version:

• Simple version: Sorting primitive integers, grades, character codes
• Object version: Sorting records, database results, or any structured data where order within equal values matters.

Conclusion

Counting Sort teaches us that sometimes the best algorithm comes from changing the fundamental approach. Instead of asking "which element is bigger?", it asks "how many of each element do I have?"

This shift from comparison to counting unlocks linear time performance that comparison-based sorts mathematically cannot achieve. The trade-off? It only works for specific data types within limited ranges.

When your data fits the mold (integers in a reasonable range), Counting Sort is often the fastest sorting algorithm you can choose.