Counting Sort


### Linear time for special cases $\Theta(n + k)$
**Pseudo-polynomial time** because there is k in [Asymptotic Notation](https://texonom.com/asymptotic-notation-44f31e0bfbaa455cb26f55423ed292a7) (because of bit transition, $log_2k$ strictly exponantial complexity). So it has a problem when $k \gt 2^n$
no comparison between elements, requires we know the value set is limited and order or value set. auxiliary storage requires length of value set. Space complexity is $\Theta(n +k)$ too.
![](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F0bf522c6-2468-4c71-99e3-68f5a25d4225%2F9b538f5a-b2b2-4456-a103-052fbb227a60%2FUntitled.png?table=block&id=c6976692-73bf-4469-803f-487077f42d2c&cache=v2)
![](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F0bf522c6-2468-4c71-99e3-68f5a25d4225%2Fd7b8b09c-99a5-44bb-bf15-aa21dba75b45%2FUntitled.png?table=block&id=ae84d89e-3493-408b-9abc-861d63bfcd97&cache=v2)
![](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F0bf522c6-2468-4c71-99e3-68f5a25d4225%2F569dad3f-eb64-43bd-b394-1246fdfb7243%2FUntitled.png?table=block&id=364545c8-9cc7-4060-b015-a30e26e27a41&cache=v2)
1. store count for each value’s count to auxiliary storage
2. change auxiliary storage to accumulated index like [Fibonacci sequence](https://texonom.com/fibonacci-sequence-830af82ec2bf49cc90da16fd1a201b14) 
3. backward, we can allocate values reducing 1 per allocate







