- counting sort solution
- Data should be in range. eg. 0-10, 90-99
- the range should be small
- can be used for chars as chars fall in 0-256
- It hashes the values in a count array and uses them for sorting.
- Create an empty array and use index to store count.
- prefix_sum can be used here to solve different problem.
- For counting sort with negative element store at 0th index.
- Can be used as sub routine for Radixsort
- TC: o(n+k), k is range
- https://www.geeksforgeeks.org/counting-sort/