Use in-place radix sort and OP's first solution with 2 iterators, coming towards each other.
If numbers in the array are not some sort of multi precision numbers and are, for example, 32-bit integers, you can sort them in 232 passes using practically no additional space (1 bit per pass). Or 28 passes and 16 integer counters (4 bits per pass).