Sort first n integers in linear time and constant space

I'm looking for a non-comparison or comparison based algorithm that can sort an array containing any permutation of the first n positive integers, which should be O(n) time开发者_如何学JAVA complexity and O(1) space complexity.

Is there an existing algorithm that fits these specifications?

If you have an array of size N with all integers from 1 to N present, you can use the following O(N) algorithm (Note: arrays are 1 based for the sake of this pseudocode so as not to introduce unnecessary complexity in explaining the algorithm):

1. Start at the first array element.
   
2. If its array index matches its value, go to the next one.
   
3. If not, swap it with the value at the array index corresponding to its value.
   
4. Repeat step 3, until no more swaps are necessary.
   
5. If not at the end of the array, go to the next array element, otherwise go to step 7
   
6. Go to step 2.
   
7. Done

In-place MSD radix sort

When you are sure that all integers are between 1 and N you can use counting sort