Counting Sort in Data Structure

What is Counting Sort in Data Structure?

Count Sort is a sorting algorithm that sorts an array by counting how many times each unique element appears in the array. The count is stored in an auxiliary array, and sorting is carried out by mapping the count to an index in the auxiliary array.

Counting Sort Algorithm

• Create an auxiliary array countArray[] with size max(inputArray[])+1 and initialize it with 0.
• Traverse the array inputArray[] then map each element to an index of count.Array[] array: execute countArray[inputArray[i]]++ for 0 <= i < N.
• Get the prefix sum for each index of the array inputArray[].
• Make an array outputArray[] of size N.
• From the end of the array inputArray[], modify outputArray[countArray[inputArray[i]] - 1] to inputArray[i]. Also, adjust countArray[inputArray[i]] to countArray[inputArray[i]]- -.

Complexity Analysis of Counting Sort Algorithm

Time Complexity

Best Case Complexity 

This occurs when no sorting is necessary, implying that the array is already sorted. The best-case time complexity for counting sort is O(n + k).

Average Case Complexity

This arises when the array elements are jumbled and do not appropriately get or descend. The average time complexity of a counting sort is O(n + k).

Worst Case Complexity

This occurs when array members must be sorted in reverse order. That is, assume you need to sort the array elements in ascending order but the elements are in descending order. The worst-case time complexity of a counting sort is O(n + k).

Space Complexity

We utilize an extra array of size K, the array's largest element, to record the frequencies of all elements in the range [0, K]. Thus, the space complexity is strongly dependent on the value of K and is equal to O(K).

Applications of Counting Sort Algorithm

• When there are numerous smaller integers, a counting sort is performed.
• When you require an algorithm with linear complexity.

Advantages of Counting Sort Algorithm

• Counting sort works best for input ranges that are similar to the number of inputs.
• Simple implementation.
• Maintains stability by retaining the relative order of equal items.

Disadvantages of Counting Sort Algorithm

• Counting sort is not compatible with decimal numbers and is only suitable for integers.
• Inefficiency occurs when value ranges are large.
• Sorting requires additional space; this is not an in-place algorithm.