What is a Counting Sort Algorithm in Data Structures? | Data Structures Tutorial

In this article, you will learn about the Counting Sort Algorithm of the Data Structure in brief.

The counting sort algorithm helps in sorting the elements of an array by counting the number of occurrences of each unrepeated element in the array. The count is stored in an additional array and the sorting is done by mapping the count as an index of an auxiliary array. 

Working of Counting Sort

1. Pick the maximum element from the given array and call it max.
2. Initialize an array of length max+1 with all the elements 0. It is used for storing the count of the elements in the array.
3. Keep the count of every element at its particular index in the count array. 
4. Keep the cumulative sum of the elements of the array. It helps in putting the elements into the correct index of the sorted array.
5. Find out the index of every element of the original array in the count array. It gives the cumulative sum. Put the element at the index.
6. Now, put every element in its correct position, and decrease its count by one.

Counting Sort Algorithm

counting_sort(array, size)

    large <- figure maximum value element in the array

    initialize count array with all zeros

    for i <- 0 to size

        put the total count of each unique element and keep the count 

        at ith index in count array

   for j <- 1 to large

        find the cumulative sum and keep it in count array i.

   for j <- size to 1

        restore the elements to the array until the count is decreased to 1.

Complexities

Time complexity

The best case complexity is O(n+k), the average case complexity is O(n+k), and the worst case complexity is O(n+k).

Space complexity is O(max)

Applications of Counting Sort

• It is used if there are smaller integers with multiple counts.
• It is used when linear complexity is needed.