Counting Sort

✅ Counting Sort

non-comparison-based sorting algorithm counting: how many times does this element appear in input array?

1. input array
   get the biggest number max
   
2. count array
   size: max +1
   

3. output array
   
   

4. get input array
   
5. get the biggest number max
   
6. make count array with size of max +1
   
7. in count array, store count of unique element of input array at their respective indices
   if 0 appears 2 times, input 2 at index 0.
   
8. store cumulative sum in count array
   
9. Update output array outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i]
   
10. also Update count array countArray[ inputArray[i] ] = countArray[ inputArray[i] ]– -
    

⭐️ Keyword

✅ Code

✅ Time complexity

O(n+k)
n: size of input array
k: size of count array(range of input value)

✅ Space complexity

O(n+k)
n: size of output array
k: size of count array

👍🏻 Pros

• stable algorithm
• if range of input is of the order of number of input, faster (when k is smaller, faster)

👎🏻 Cons

• does not work for decimal value
• not in-place sorting algorithm

💡 Reference

https://www.geeksforgeeks.org/counting-sort/?ref=shm