Count sort in C C++
Count sort is index based sorting algorithm. It is much faster than comparison based sorting technique but takes a lot more space.
We initialise an array T with of size equal to the 1 + greatest element in the list/array A that needs to be sorted and set value of all elements of T as 0 initially.
Now loop/iterate through our main array A and increment the element of array T at index equal to the element of array A . Like first element is 6 so increment element at index 6 of the array T.
So we obtain the following array T.
Now loop/iterate through this array T, and if the element has value greater that 0, assign that index to the array A and decrement the value at that index of array T.
Like in array T, at index 3 value is 2, that is, greater than 0 so assign value 2 to the first element of our main array A and then decrement the value 2 to 1. Iterate further and assign the next obtained value to 2nd element of A and continue.
Time complexity of count sort is O(n).