What is counting sort?

The counting sort algorithm sorts an array’s contents by counting the repetition of each element that occurs in the array. A counting sort algorithm is a stable algorithm that works the best when the range of elements in the array is small, say for example from 0 to 9. The count which is the number of repetitions of an element in the array is mapped to an index of an auxiliary array, which is then saved in an auxiliary array. The counting sort algorithm has a stable time complexity of the order of O(size of array + size of auxiliary array). Let’s discuss the algorithm in detail as follows.

Counting sort algorithm

The counting sort algorithm is given as follows:

function Counting_Sort(ARRAY, SIZE) 

                maximum -> Find the maximum element in the given array.  

                Create the count array C with length ->  maximum + 1  

                Initialize C with all 0's  

                For q equal to 0 to length, do :

                           Find the number of repetitions R of every value from 0 to maximum, in ARRAY   

                           Store R at (q)th position in C

               End For 

               For u equal to 1 to maximum, do:

                            Now, find the cumulative sum and store it in C

                           Rotate the values in C clockwise by 1 position

               End For

               For w equal to 0 to SIZE, do:

                          For each w element in ARRAY, map it to a new array NEW_ARRAY of size SIZE, based on the R value in the count array C 

                          Increment the R of every restored element by 1, so that it is placed at one place greater in the NEW_ARRAY.

              END For  

End Counting_Sort(ARRAY, SIZE).

This sorting strategy uses the above procedure and is based on the frequency or count of distinct elements to be sorted.

Example

Let’s take an example of an array ARRAY = [1,0,3,1,3,1] 

• Firstly, find the maximum element in the array and set it to the maximum. Here, it is 3.
• Create an array repetitions that will store the number of repetitions R of each element at their index. Make its size equal to "maximum+1" and initialize all elements to 0.
• Store the number of repetitions at the corresponding index of each value in the array Repetitions, as shown in the Table given as follows.

• Change the values in the Repetitions array by adding the previous values at previous indexes to produce the cumulative sum of an array. This is shown in the array below.

• Move the values clockwise by 1 place, as shown below.

• Since the array ARRAY has 6 values, create a new array NEW_ARRAY with six places to store the sorted values. Map each value in ARRAY at the appropriate place in the NEW_ARRAY using the array Repetitions to denote the index. After this increment the value at the place in array Repetitions by 1 after the corresponding value is placed in NEW_ARRAY, all this is shown in tables below.

Repetitions array:

ARRAY and NEW_ARRAY array:

• The sorted array NEW_ARRAY is shown below.

Analysis of time complexity

The time taken to find the maximum number in the array will be equal to the order of O(maximum number +1). This is because it will be found among all elements starting from 0 and at worst case the big O complexity will be O(SIZE), where SIZE is equal to the maximum number +1. 

The sorting is done by iterating over the input array linearly. Thus, it will take a time equal to the O(Size of ARRAY). 

Hence, it will take a total time of the order of O(Size of ARRAY + Size of Repetitions array).

Counting sort usage

Counting sort is a reliable sorting method that works the best when the range of elements in the array is small, say for example from 0 to 9. The count which is the number of repetitions of an element in the array is mapped to an index of an auxiliary array, which is then saved in an auxiliary array. This sorting strategy works effectively when the difference between distinct keys isn’t too significant. Otherwise, it adds to the space complexity.

Counting sort can be used when

• the array consists of repeated elements with smaller value.
• the demand is for linear complexity.

Points to remember when using counting sort

• The counting sort implementation shown above may also sort negative input numbers.
• Counting sort can be used as a subprogram in other sorting algorithms, such as radix sort, which is good for sorting well-defined, finite, and tiny integers.
• If the range of input data (m) is not substantially more than the number of elements (n) in the input array, counting sort technique is efficient. When the number of elements are more, the repetitions array will take much space and time for initialization. Thus, it works efficiently when the range of values is small.
• In contrast to comparison-based algorithms, it is an integer-based sorting method. Comparing pairs of integers is the sole way to sort numbers using a comparison-based sorting algorithm. Comparison-based sorting algorithms include quick sort, merge sort, bubble sort, selection sort, heap sort, and insertion sort while non-comparison-based sorting algorithms include radix sort, bucket sort, and comparison sort.

Advantages of counting sort

• Couting sort is an efficient algorithm for sorting arrays having the values that falls within a smaller range.
• A stable algorithm.
• For a sorting algorithm to be stable, the order of elements in the sorted array with equal keys (values) must match the order of the input array.

Disadvantages of counting sort

• Couting sort is not designed for sorting huge amounts of data.
• Cannot be used for sorting string values.
• Because an array of frequencies cannot be formed without counting sort, it can only be used for arrays with integer elements.

Context and Applications

This topic is important for postgraduate and undergraduate courses, particularly for, 

• Bachelors in Computer Science Engineering.
• Associate of Science in Computer Science.

Common Mistakes

• The counting sort implementation shown above may also sort negative input numbers.
• Counting sort can be used as a subprogram in other sorting algorithms, such as radix sort, which is good for sorting well-defined, finite, and tiny integers.
• If the range of input data (m) is not substantially more than the number of elements (n) in the input array, counting sort technique is efficient. When the number of elements are more, the repetitions array will take much space and time for initialization. Thus, it works efficiently when the range of values is small.
• In contrast to comparison-based algorithms, it is an integer-based sorting method. Comparing pairs of integers is the sole way to sort numbers using a comparison-based sorting algorithm. Comparison-based sorting algorithms include quick sort, merge sort, bubble sort, selection sort, heap sort, and insertion sort while non-comparison-based sorting algorithms include radix sort, bucket sort, and comparison sort.

Practice Problems

Question 1: When using counting sort to sort the array arr=1,5,3,8,2, how many comparisons will be made?

1. 5
2. 7
3. 3
4. None of these

Answer: Option 4 is correct.

Explanation: Because counting sort is an example of a non-comparison sort, it can sort an array without performing comparisons.

Question 2: Which of the following methods of sorting is the most stable sorting?

1. bubble sort
2. counting sort
3. radix sort
4. bucket sort

Answer: Option 2 is correct.

Explanation: Counting sort is a stable sorting method because elements with identical values appear in the same order in the output array as they did in the input array.

Question 3: If the range of input data is not much bigger than the number of elements to be sorted, which of the following sorting procedures is the most efficient?

1. selection sort
2. bubble sort
3. counting sort
4. insertion sort

Answer: Option 3 is correct.

Explanation: The counting sort has a time complexity of O(n+k), where n is the number of input elements and k is the input range. As a result, if the input range is not much larger than the number of elements in the array, it is quite efficient.

Question 4: What is the counting sort's auxiliary space requirement?

1. O(1)
2. O(n)
3. O(log n)
4. O(n+m) m=range of input

Answer: Option 4 is correct.

Explanation: To sort the input array, counting sort utilizes two additional arrays. The size of the first array is m because it must contain the count of all the elements that fall within the range of input data elements. Because the second array must store the input elements in sorted order, its size is n. As a result, the total amount of auxiliary space required is O(n+m).

Question 5: Which of the following requires the most auxiliary storage space when sorting?

1. Bubble sort
2. Counting sort
3. Quicksort
4. Heapsort

Answer: Option 2 is correct.

Explanation: Quicksort, bubble sort, and heap sort are in position sorting algorithms, but counting sort requires O(n+k) auxiliary space. As a result, counting sort takes up the extra space.