Indeed. Usually if you get question such as "you have an array of 1 through n", the immediate thought should be "why is it just up to n and not arbitrary numbers"? From there, you know you can get a linear sort by leveraging the mutual relationships between these numbers.