The fastest way to sort an array without overwriting it

Question

I want to sort an int[] array in Java, but save the sorted array as a new array, and not overwrite it.

The most obvious way to do this is to create a copy of the array, and then sort this new array as follows:

 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" when we copy the elements of the old array to the new?

Answer 1

you can use

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

But I doubt it faster than

 int[] a2 = Arrays.copyOf(a, a.length); Arrays.sort(a2); 

Regardless of the fact that this is the same complexity, so do not expect more than a constant acceleration of the factor.

Answer 2

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

Copies an array from the specified source array, starting at the specified position, to the specified position of the target 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:. While you are asking for a faster way to sort the array, as you saw, there is a long discussion about whether there would be a better option for copying or sorting on the fly. To do this, you can try to make some benchmark. But if you use a copy for sorting , you will find here that depends on the size and elements of the array .

Answer 3

If you tend to use 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 check the difference and actually depends on the size of the data as well as the data in the array.

However, I cannot comment on how deterministic this method is, but I am sure that I will conduct several experiments and publish my results here.

UPDATE:

I used the following code to test TreeSet performance

 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 a 64-bit Core-i7 system with Java 8:

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

From these results it is clear that TreeSet is much slower than sorting a duplicate array. Good exercise for me.

Answer 4

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