Fastest way to sort an array without overwriting it

To sort a new array while iterating the old won't be faster. For this you can use System.arraycopy() instead of create your own sorting or copy function.

Copies an array from the specified source array, beginning at the specified position, to the specified position of the destination array.

Example:

int[] a1 = new int[]{1,2,3,4,5};  // I suppose a1...
int[] a2 = new int[a1.length];

System.arraycopy( a1, 0, a2, 0, a1.length );

Arrays.sort(a2);

---

UPDATE: As long as you are asking for the faster way of sort an array, as you have seen there is a long discussion about if copying it or sorting on the fly will be best option. For that you can try to make some benchmark. But if you use copy to sort it you will find here that all depends of the size and elements of the array..

You could use

int[] a2 = IntStream.of(a).sorted().toArray();

But I doubt it's faster than

int[] a2 = a.clone();
Arrays.sort(a2);

Regardless it's the same complexity, so don't expect more than a constant factor speedup.