**Counting Sort** is an efficient, non-comparative sorting algorithm that counts the occurrences of each unique element in the input array. It then uses this count information to place elements in their correct positions in the output array. Unlike comparison-based algorithms such as Quick Sort and Merge Sort, Counting Sort is most effective when dealing with integer values and a known range of data.

This post will cover how Counting Sort works, its JavaScript implementation, and a step-by-step algorithm explanation. We’ll also discuss its time and space complexities and where you might want to use it.

**What is Counting Sort?**

Counting Sort works by counting the number of occurrences of each distinct element in the input array and using this count to determine the position of each element in the output array. It is particularly effective when the range of the input values is not too large, and the elements are integers.

Counting Sort is **stable**, meaning it preserves the relative order of elements with equal values.

**Pseudocode for Counting Sort**

Here’s the pseudocode for **Counting Sort**:

procedure countingSort(arr, maxValue) # Step 1: Create the count array count = new array of size maxValue + 1, initialized to 0 # Step 2: Count the occurrences of each element for i = 0 to length(arr) - 1 do count[arr[i]] = count[arr[i]] + 1 # Step 3: Modify the count array to store cumulative counts for i = 1 to maxValue do count[i] = count[i] + count[i - 1] # Step 4: Create the output array and place elements at correct positions output = new array of size length(arr) for i = length(arr) - 1 down to 0 do output[count[arr[i]] - 1] = arr[i] count[arr[i]] = count[arr[i]] - 1 # Step 5: Copy the sorted output array back to the original array for i = 0 to length(arr) - 1 do arr[i] = output[i]

**Time Complexity of Counting Sort**

**Best Case**: O(n + k) – where`n`

is the number of elements in the array and`k`

is the range of the input data (maxValue). The time complexity depends linearly on both the number of elements and the range of the input.**Average Case**: O(n + k) – Similar to the best case.**Worst Case**: O(n + k) – The worst-case time complexity is still linear, making Counting Sort efficient for small ranges of integers.

**Space Complexity of Counting Sort**

**Space Complexity**: O(n + k) – Counting Sort requires additional space for the`count`

array (size`k + 1`

) and the`output`

array (size`n`

).

**JavaScript Implementation of Counting Sort**

Let’s implement **Counting Sort** in JavaScript based on the pseudocode.

// Counting Sort implementation in JavaScript function countingSort(arr, maxValue) { // Step 1: Create and initialize the count array let count = new Array(maxValue + 1).fill(0); // Step 2: Count the occurrences of each element for (let i = 0; i < arr.length; i++) { count[arr[i]]++; } // Step 3: Modify the count array to store cumulative counts for (let i = 1; i <= maxValue; i++) { count[i] += count[i - 1]; } // Step 4: Create the output array and place elements in the correct positions let output = new Array(arr.length); for (let i = arr.length - 1; i >= 0; i--) { output[count[arr[i]] - 1] = arr[i]; count[arr[i]]--; } // Step 5: Copy the output array back to the original array for (let i = 0; i < arr.length; i++) { arr[i] = output[i]; } return arr; } // Example usage const arr = [4, 2, 2, 8, 3, 3, 1]; const maxValue = Math.max(...arr); console.log("Original array:", arr); console.log("Sorted array:", countingSort(arr, maxValue));

**Step-by-Step Explanation of the Code**

**Create the Count Array**:- We first create a
`count`

array of size`maxValue + 1`

, where`maxValue`

is the largest value in the input array. This array will store the number of occurrences of each element in the input array. - The array is initialized with zeroes using
`.fill(0)`

.

- We first create a
**Count the Occurrences of Each Element**:- We iterate through the input array and, for each element, increment the corresponding index in the
`count`

array. For example, if the element is`4`

, we increment`count[4]`

by`1`

.

- We iterate through the input array and, for each element, increment the corresponding index in the
**Modify the Count Array**:- Next, we modify the
`count`

array so that each element at index`i`

contains the cumulative count of elements up to index`i`

. This will give us the correct positions of each element in the sorted array.

- Next, we modify the
**Place Elements in the Output Array**:- We create an
`output`

array and iterate over the input array in reverse order to maintain the stability of the sorting. For each element, we place it in its correct position in the`output`

array based on the cumulative counts stored in the`count`

array.

- We create an
**Copy the Output Array Back**:- Finally, we copy the sorted
`output`

array back into the original array, completing the sorting process.

- Finally, we copy the sorted

**Step-by-Step Walkthrough of Counting Sort** with Array

Let’s walk through Counting Sort using the array `[4, 2, 2, 8, 3, 3, 1]`

.

**Step 1: Create the Count Array**

- The largest element in the array is
`8`

, so the`count`

array will have`9`

slots (from 0 to 8). - Initially, the
`count`

array is:`[0, 0, 0, 0, 0, 0, 0, 0, 0]`

.

**Step 2: Count the Occurrences of Each Element**

- For each element in the array, increment the corresponding index in the
`count`

array:- After processing the array, the
`count`

array becomes:`[0, 1, 2, 2, 1, 0, 0, 0, 1]`

. - This means there is one occurrence of
`1`

, two occurrences of`2`

, two occurrences of`3`

, one occurrence of`4`

, and one occurrence of`8`

.

- After processing the array, the

**Step 3: Modify the Count Array**

- Convert the
`count`

array into a cumulative count array:- The modified
`count`

array is:`[0, 1, 3, 5, 6, 6, 6, 6, 7]`

. - This array now tells us the position of each element in the sorted array.

- The modified

**Step 4: Place Elements in the Output Array**

- Iterate through the input array in reverse and place each element in its correct position in the
`output`

array:- The output array after this step:
`[1, 2, 2, 3, 3, 4, 8]`

.

- The output array after this step:

**Step 5: Copy the Output Array Back**

- Copy the sorted
`output`

array back into the original array:- The sorted array is now
`[1, 2, 2, 3, 3, 4, 8]`

.

- The sorted array is now

**Pros and Cons of Using Counting Sort**

**Pros**:

**Linear Time Complexity**: Counting Sort runs in linear time for arrays with a known and small range of integer values, making it highly efficient compared to comparison-based algorithms.**Stable Sorting Algorithm**: Counting Sort preserves the relative order of elements with equal values, making it stable and suitable for applications where stability is essential.**Non-Comparative Sorting**: Counting Sort doesn’t rely on element comparisons, which can make it faster than comparison-based algorithms for specific data types.

**Cons**:

**Requires Extra Space**: Counting Sort requires additional space proportional to the range of input values (`k`

), which can be a disadvantage if the range is large.**Limited to Integer Data**: Counting Sort is primarily used for sorting integers or data that can be mapped to integers. It’s less suitable for floating-point numbers or strings.**Inefficient for Large Ranges**: When the range of input values is large, Counting Sort requires a lot of space and time, making it less practical for datasets with a wide range of values.

**When to Use Counting Sort**

Counting Sort is a great choice when:

**You know the range of the input values**: Counting Sort performs best when the range (`k`

) of input values is known and relatively small.**You need a stable sorting algorithm**: If maintaining the relative order of equal elements is important, Counting Sort’s stability makes it a good choice.**Sorting integers**: Counting Sort

**Conclusion**

**Counting Sort** is an efficient, non-comparative sorting algorithm that performs exceptionally well for datasets with a known and small range of integer values. Its linear time complexity makes it faster than comparison-based algorithms in specific cases, and its stability ensures that the relative order of equal elements is preserved. While the extra space required can be a drawback for large ranges, Counting Sort’s simplicity and speed make it a go-to option for specific applications.

Moreover, Counting Sort is often used in algorithms like **Radix Sort** to sort numbers by individual digits. It ensures that the sorting remains stable and efficient at each step, helping Radix Sort sort large datasets of numbers quickly.

Congratulations on reading to the end of the tutorial!

Read the following articles to learn how to implement Counting Sort:

In Python – How to do Counting Sort in Python

In C++ – How to do Counting Sort in C++

Have fun and happy researching!

Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.