Fastest way to sort an array without overwriting it

Question

I want to sort an int[] array in Java, but store the sorted array as a new array instead of overwriting it.

The most obvious way to do this seems to be to create a copy of the array and then sort that new array, like so:

int[] a2 = new int[a.length];

for (int i = 0; i < this.length; i++) {
    a2[i] = a[i];
}

Arrays.sort(a2);

However, is there a faster way? Can we sort 'at the same time' as we copy the elements of the old array into the new one?

Answer 1

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.

Answer 2

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..

Answer 3

If you are inclined towards using TreeSet, the following code may serve the purpose:

TreeSet<Integer> copied = new TreeSet<>();
for (int i = 0; i < array.length; i++) {
    copied.add(i);
}

I tried to test the difference and it actually depends on the size of the data as well as data in the array.

However, I cannot comment on how deterministic is this method, but I sure will run a few experiments and post my findings here.

UPDATE:

I used the following code to test the performance of TreeSet

import java.util.Arrays;
import java.util.Random;
import java.util.TreeSet;

class TestArrayCopy {

    public static void main(String[] arg) throws java.io.IOException {
        for (int i = 1; i <= 10; i++) {
            int arr[] = randomArray();
            System.out.println("Array Size: " + arr.length + ". Results for case #" + i);
            System.out.println("Using Array Copy:");
            copyAndSort(arr);
            System.out.println("Using Tree Set:");
            useTreeSet(arr);
            System.out.println("----------------------------");
        }
    }

    public static void copyAndSort(int array[]) {
        long start = System.nanoTime();
        for (int j = 0; j < 100; j++) {
            int copied[] = Arrays.copyOf(array, array.length);
            Arrays.sort(copied);
        }
        long end = System.nanoTime();
        System.out.println(end - start);
    }

    public static void useTreeSet(int array[]) {
        long start = System.nanoTime();
        for (int j = 0; j < 100; j++) {
            TreeSet<Integer> copied = new TreeSet<>();
            for (int i = 0; i < array.length; i++) {
                copied.add(i);
            }
        }
        long end = System.nanoTime();
        System.out.println(end - start);
    }

    public static int[] randomArray() {
        Random random = new Random();
        int len = 100000 + random.nextInt(1000000);
        int arr[] = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = random.nextInt(1000000);
        }
        return arr;
    }

}

The following results were achieved on Core-i7 64-bit System with Java 8:

Array Size: 616568. Results for case #1
Using Array Copy:
7692926921
Using Tree Set:
16336650396
----------------------------
Array Size: 390270. Results for case #2
Using Array Copy:
4441066232
Using Tree Set:
9306742954
----------------------------
Array Size: 658410. Results for case #3
Using Array Copy:
8534144532
Using Tree Set:
17721764026
----------------------------
Array Size: 1021396. Results for case #4
Using Array Copy:
13573512678
Using Tree Set:
31341152398
----------------------------
Array Size: 1034872. Results for case #5
Using Array Copy:
13298690836
Using Tree Set:
30950793986
----------------------------
Array Size: 466014. Results for case #6
Using Array Copy:
5501196272
Using Tree Set:
11704757934
----------------------------
Array Size: 190231. Results for case #7
Using Array Copy:
1662270714
Using Tree Set:
4465174267
----------------------------
Array Size: 681150. Results for case #8
Using Array Copy:
8262756493
Using Tree Set:
19079310588
----------------------------
Array Size: 627257. Results for case #9
Using Array Copy:
6725984653
Using Tree Set:
14468898852
----------------------------
Array Size: 397189. Results for case #10
Using Array Copy:
3122214311
Using Tree Set:
7356182877
----------------------------

From these results, it can be seen that TreeSet is a lot slower than sorting a duplicate array. Good exercise for me.

Answer 4

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