Counting Sort Algorithm

Counting Sort Algorithm

Counting sort is an algorithm for sorting a collection of objects according to the keys between a specific integer range

It works based on counting the number of objects with specific keys and doing some arithmetic operations to calculate the positions of the objects in the output sequence.


Input array: [1, 4, 4, 3, 3, 5, 5, 6, 7, 2, 4]
Output array: [1, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7]

1) In count array to store the count of each element.
Range of elements in the array is 0 to 7 (maximum element)

Index array :


Count array is :

2) Update count array such that at each index store the sum of itself and previous count.

3) Output each object from the input sequence by decreasing the count.
Places of elements:

Output will be: [1, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7]


Time complexity: O(nlogn), n is size of the array

a. First get the maximum element of the array by traversing in the array and store it in Range.

b. Create a count array of size of Range + 1 and initialize with zeroes.

c. Update the array with count of elements in the array according tothere indexes. Store the count of i at index i.

d. Now, update the count array such that at each index  element stores the sum of itself and previous element.

e. Create an auxiliary output array.

f. In this output array store the elements from the input array according to count array, if count[i] = k, store i in k. and decrease the count[i] = count[i] – 1. Do it for all the elements in the input array.

g. Copy the output array into the input array.
Input_array[i] = output[i]

h. Finally print the sorted input array.

Algorithm working