Sparse Key Counting Sort
Sparse Key Counting Sort Sparse key counting sort handles large key ranges by storing counts only for keys that appear in the input. It replaces the dense count array of counting sort with a map from key to frequency. This is useful when the key universe is huge but the number of distinct keys is small. Problem Given an array $A$ of $n$ keys drawn from a large domain, sort...