Counting Sort
Counting Sort is a wellknown sorting algorithm in computer science. It’s an integer sorting algorithm, unlike comparisonbased algorithms like Quick Sort or Merge Sort.
Here’s a quick overview of how Counting Sort works:
Find the Range: Determine the range of input values (minimum and maximum values).
Count the Occurrences: Create a counting array of size equal to the range, and initialize all elements to 0. Then, iterate through the input array and increment the count of each value in the counting array.
Calculate the Cumulative Count: Modify the counting array by storing the cumulative count of occurrences. This step helps determine the position of each element in the sorted array.
Build the Sorted Array: Iterate through the input array, and for each value, place it in the sorted array at the position indicated by the cumulative count in the counting array. Decrement the count in the counting array for that value.
Copy Back to Original Array: Copy the sorted values back to the original input array if necessary.
Key Properties
 Stable: If implemented correctly, it maintains the relative order of equal elements.
 Not ComparisonBased: It doesn’t compare elements against each other, unlike most other sorting algorithms.
 Time Complexity: O(n + k), where n is the number of elements, and k is the range of input values.
 Space Complexity: O(k) for the counting array.
Limitations
 It can only sort integers (or objects that can be mapped to integers).
 It may not be efficient if the range of input values (k) is much larger than the number of elements (n), as it requires space proportional to the range.
Counting Sort is often used as a subroutine in other sorting algorithms like Radix Sort, and it’s particularly effective when dealing with a small range of integer values.
Description
Counting Sort is a noncomparative integer sorting algorithm. Unlike comparisonbased sorting algorithms like Quick Sort, Counting Sort sorts integers within a specific range. It works by counting the occurrences of each value in the input array, then using that count to place each value in its correct position in the sorted array. It’s often useful when the range of integers is relatively small compared to the number of elements to be sorted.
Solution
Let’s look at the code for implementing Counting Sort in Java, C++, and Python.
Java
In Java, you can use an array to store the counts of each integer. Here’s a stepbystep guide:
 Determine the minimum and maximum values in the array.
 Create a counting array of size equal to the range.
 Count the occurrences of each value.
 Calculate the cumulative count.
 Build the sorted array using the cumulative count.
 Copy the sorted values back to the original array if necessary.


C++
In C++, you can use a similar approach, with vectors to handle the counting.


Python
Python’s higherlevel syntax allows for a more concise implementation:


The code in all three languages follows a similar pattern and performs the sort inplace, meaning the original array is sorted without needing to return a new one. The time complexity in all cases is O(n + k), where n is the number of elements, and k is the range of input values. The space complexity is O(k) for the counting array.
title: Countingsort excerpt: This covers the countingsort algorithm and implementation. tags: arrayfrequencycounter
The O(N log N) performance can be beaten if the method used is other than comparisons to sort. Countingsort can sort in less than O(N log N) time.
Implementation
Countingsort works if the values to sort are integers that lie in a relatively small range. The frequence of items in the array is counted. The numbers are copied back into the array in order and based on their frequency multiple elements will be copied.


The max parameter is the largest value in the array. The initial frequency of count for all numbers is initialized to zero. The frequency of every element in array is calculated and stored in the counts array. The last step is copying the values back into the original array. Each value is copied once, so it takes N steps. The elements with zero frequency is skipped.
In the worst case, if all the values are the same, so that the counts array contains mostly 0s, it takes M steps to skip over the 0 entries. The total run time is O(2 x N + M) = O(N + M). If M is relatively small compared to N, this is much smaller than the O(N log N).
Building Block
 Array Frequency Counter