Since 1,2,...,n is finite, use a bit array to represent them. See the telephone number sorting example in Column 1 of <Programming Pearls> (Jon Bentley) for detailed explanation.

Back to Data Structures Problems...