Calculate frequencies, then use bucket sort where index represents frequency count, achieving O(n) linear time without a heap.