Linear Sorts: Counting Sort

What is Counting Sort Algorithm?

• Counting sort is an integer sorting algorithm used in computer science to collect objects according to keys that are small positive integers.
• It works by determining the positions of each key value in the output sequence by counting the number of objects with distinct key values and applying prefix sum to those counts.
• Because its running duration is proportional to the number of items and the difference between the maximum and minimum key values, it is only suited for direct usage when the number of items is not much more than the variation in keys.
• It's frequently used as a subroutine in radix sort, a more efficient sorting method for larger keys.
• Average Case Time Complexity: O(n+k), where k is the range of the non-negative key values.
• Worst Case Time Complexity: O(n+k), where k is the range of the non-negative key values.

Example:

Iterating through the input, counting the number of times each item appears, and utilizing those counts to compute each item's index in the final, sorted array is how counting sort works.

Consider a given array that needs to be sorted. First, you’ll have to find the largest element in the array and set it to the max.

To store the sorted data, you will now initialize a new count array with length "max+1" and all elements set to 0.

Later, as shown in the figure, you will store elements of the given array with the corresponding index in the count array.

Now, you will change the count array by adding the previous counts to produce the cumulative sum of an array, as shown below:

Because the original array has nine inputs, you will create another empty array with nine places to store the sorted data, place the elements in their correct positions, and reduce the count by one.

As a result, the sorted array is:

Reference:

To learn more about Counting Sort: Counting Sort Algorithm: Overview, Time Complexity & More.