I think it's important to mention that counting sort and radix sort are not "true" comparison-based sorts: they have additional requirements on the input data.
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.
Comments
I think it's important to mention that counting sort and radix sort are not "true" comparison-based sorts: they have additional requirements on the input data.
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.