JavaScript Program to Implement Counting Sort

This post shows how to implement Counting Sort in JavaScript — a non-comparison-based sorting algorithm that can sort certain kinds of data faster than O(n log n), by counting occurrences instead of comparing elements.

Counting sort in JavaScript:

Explanation:
Counting sort works by counting how many times each value appears in the array, storing those counts in a separate array, and then using those counts to place each value directly into its correct sorted position. It doesn't compare elements to each other at all, which is why it can beat the O(n log n) limit of comparison-based sorts — but it only works well when the range of input values is known and reasonably small.

---

---

JavaScript Program to Implement Counting Sort

function countingSort(arr) {
  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);

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

  const result = [];
  for (let i = 0; i <= max; i++) {
    while (count[i] > 0) {
      result.push(i);
      count[i]--;
    }
  }

  return result;
}

const numbers = [4, 2, 2, 8, 3, 3, 1];
console.log("Sorted array:", countingSort(numbers));

Output:

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

Counting sort trades generality for speed — it only works on non-negative integers within a known range. For general-purpose sorting, Merge Sort or Quick Sort are more broadly applicable. Try it with different inputs in our Code Runner.

---

Frequently Asked Questions About Counting Sort in JavaScript

What is the time complexity of counting sort?

Counting sort runs in O(n + k) time, where n is the number of elements and k is the range of input values. This can beat O(n log n) comparison sorts when k is small relative to n.

Why doesn't counting sort work well for all kinds of data?

It requires the input to be non-negative integers (or easily mapped to them) within a known, reasonably small range. Sorting arbitrary strings, floating-point numbers, or integers with a huge range makes counting sort impractical due to memory usage.

Is counting sort a comparison-based sorting algorithm?

No. Unlike merge sort, quick sort, or bubble sort, counting sort never compares two elements directly — it sorts by counting occurrences of each value, which is why it can bypass the O(n log n) lower bound that applies to comparison sorts.