Why is ArrayList's sort method faster than Arrays' in Java?

Question

The goal of the following code is to sort 300,000 int numbers. I find that the duration of ArrayList's sort() is less than Arrays' sort(). Internally, they use the same algorithm to sort. ArrayList uses Arrays' sort() to sort its element data.

public class EasySort {
 public static void main(String args[]) {
 // Read data from file, number split by ","
 FileReader fr = null;
 try {
 fr = new FileReader("testdata2.txt");
 } catch (FileNotFoundException e) {
 // TODO Auto-generated catch block
 e.printStackTrace();
 }
 BufferedReader bufferedReader=new BufferedReader(fr);
 String line=null;
 try {
 line=bufferedReader.readLine();
 } catch (IOException e) {
 // TODO Auto-generated catch block
 e.printStackTrace();
 }
 // use split method to generate a String array to save numbers
 String[] strArray=line.split(",");
 //Convert string array to ArrayList<Integer>
 ArrayList<Integer> integerList=new ArrayList<>();
 for(String str:strArray){
 integerList.add(Integer.parseInt(str));
 }
 //Sort by ArrayList
 long t0=System.currentTimeMillis();
 integerList.sort(((p1,p2)->(p1.intValue()<p2.intValue()?-1:p1.intValue()>p2.intValue()?1:0)));
 long t1=System.currentTimeMillis();
 System.out.println("ArrayList Sort duration:"+(t1-t0));
 //Convert string array to Integer array
 Integer[] integerArray=new Integer[strArray.length];
 int i=0;
 for(String str:strArray){
 integerArray[i++]=Integer.parseInt(str);
 }
 //Sort by Arrays
 t0=System.currentTimeMillis();
 Arrays.sort(integerArray, ((p1,p2)->(p1.intValue()<p2.intValue()?-1:p1.intValue()>p2.intValue()?1:0)));
 t1=System.currentTimeMillis();
 System.out.println("Arrays duration:"+(t1-t0));
 }
}

The result is as follows:
ArrayList Sort duration:211
Arrays duration:435

I checked the source code of ArrayList. It use Arrays.sort() in its own sort method.

 @Override
 @SuppressWarnings("unchecked")
 public void sort(Comparator<? super E> c) {
 final int expectedModCount = modCount;
 Arrays.sort((E[]) elementData, 0, size, c);
 if (modCount != expectedModCount) {
 throw new ConcurrentModificationException();
 }
 modCount++;
 }

So, in my opinion, my code should show the same duration. But I tried many times, and the results are similar. What happened?

Java version: 8
Operating System: Windows 7

• Kaustubh Khare: Possible duplicate of Collections vs Arrays regarding sort()
• OLIVER.KOO: which Java version you using?
• prasad_: List<Integer> can be sorted without a comparator (Integer already implements Comparable); so, integerList.sort(null) will do. And, is it required to create Integer [] integerArray? Use an array of primitive int's; and use Arrays.sort(intArray). You may see different results.
• zhh: How many times had you tried? I have tested on my machine with ArrayList<Integer> and Integer[], they are almost the same time.
• Andy Turner: How do I write a correct microbenchmark in Java

Answer 1

This is a warm-up issue - but exactly why I don't know.

Using this code:

public void test() {
 Integer[] a = randomData(10000000);
 ArrayList<Integer> integerList = new ArrayList<>();
 for (Integer i : a) {
 integerList.add(i);
 }
 long t0, t1;
 //Sort by ArrayList
 t0 = System.currentTimeMillis();
 integerList.sort(((p1, p2) -> (p1.intValue() < p2.intValue() ? -1 : p1.intValue() > p2.intValue() ? 1 : 0)));
 t1 = System.currentTimeMillis();
 System.out.println("ArrayList duration:" + (t1 - t0));
 //Sort by Arrays
 Integer[] integerArray = Arrays.copyOf(a, a.length);
 t0 = System.currentTimeMillis();
 Arrays.sort(integerArray, ((p1, p2) -> (p1.intValue() < p2.intValue() ? -1 : p1.intValue() > p2.intValue() ? 1 : 0)));
 t1 = System.currentTimeMillis();
 System.out.println("Arrays duration:" + (t1 - t0));
}
Random r = new Random(System.currentTimeMillis());
private Integer[] randomData(int n) {
 Integer[] a = new Integer[n];
 for (int i = 0; i < n; i++) {
 a[i] = r.nextInt();
 }
 return a;
}

and moving the two sorts into different orders I get:

Arrays duration:4209

ArrayList duration:4570

ArrayList duration:6776

Arrays duration:4684

So if ArrayList is sorted first it takes longer.

So @AndyTurner's comment is correct - refer to How do I write a correct micro-benchmark in Java?

Java 8 - Windows 10

• astafev.evgeny: if it's warmup, why arraylist numbers are worse even if it goes after array? also interesting behaviour - if you decrease array size, arraylist sorting will be faster in any position
• Jerry Chin: JIT and other Java optimization techniques make it very hard to correctly setup micro-benchmark.

Answer 2

They should be the same, I dont know why you had different results. Below is my code and I have almost the same time. For T[] and ArrayList<T> both will invoke Arrays.sort(T[], ...) which will then use merge sort or tim sort.

Random rand = new Random();
Integer[] array = new Integer[300000];
for (int i = 0; i < array.length; i++)
 array[i] = rand.nextInt(array.length); 
ArrayList<Integer> list = new ArrayList<>(Arrays.asList(array)); 
long a = System.currentTimeMillis();
Arrays.sort(array, 0 ,array.length);
long b = System.currentTimeMillis();
list.sort(null);
long c = System.currentTimeMillis();
System.out.println(b - a);
System.out.println(c - b);

• David.Ren: I have run your code , b-a=446, c-d=91. My Java version is 8. Which is yours?
• zhh: @David.Ren I got both 220~240, My java version is 7.

Answer 3

This is something I tried using Java 8. Note that there is an array is of ints, an array of Integers and the List is of Integers. In addition the Integer array is sorted using the Arrays.parallelSort().

import java.util.*;
import java.util.stream.*;
public class TestingSorts {
 public static void main(String[] args) {
 long t0 = 0L;
 long t1 = 0L;
 // Run this procedure 10 times
 for (int i = 1; i < 11; i++) {
 // Create an int array and Integer List filled with random numbers
 int [] intArray = IntStream.generate(() -> new Random().nextInt())
 .limit(300_000)
 .toArray();
 Integer [] integerArray = IntStream.generate(() -> new Random().nextInt())
 .limit(300_000)
 .boxed()
 .toArray(n -> new Integer[n]);
 Integer [] integerArrayP = IntStream.generate(() -> new Random().nextInt())
 .limit(300_000)
 .boxed()
 .toArray(n -> new Integer[n]);
 List<Integer> intList = IntStream.generate(() -> new Random().nextInt())
 .limit(300_000)
 .boxed()
 .collect(Collectors.toCollection(ArrayList::new));
 // Sort the List and the arrays
 t0 = System.currentTimeMillis();
 intList.sort(null);
 t1 = System.currentTimeMillis();
 System.out.println(i + ") ArrayList<Integer> sort duration: " + (t1 - t0));
 t0 = System.currentTimeMillis();
 Arrays.sort(integerArray, Comparator.naturalOrder());
 t1 = System.currentTimeMillis();
 System.out.println(i + ") Integer[ ] sort duration: " + (t1 - t0));
 t0 = System.currentTimeMillis();
 Arrays.parallelSort(integerArrayP, Comparator.naturalOrder());
 t1 = System.currentTimeMillis();
 System.out.println(i + ") Integer[ ] PARALLEL sort duration: " + (t1 - t0));
 t0 = System.currentTimeMillis();
 Arrays.sort(intArray);
 t1 = System.currentTimeMillis();
 System.out.println(i + ") int[ ] sort duration: " + (t1 - t0));
 }
 }
}

Results (on a Windows 7 64 bit OS running on CORE i3 processor):

1) ArrayList<Integer> sort duration: 200
1) Integer[ ] sort duration: 424
1) Integer[ ] PARALLEL sort duration: 414
1) int[ ] sort duration: 136
2) ArrayList<Integer> sort duration: 143
2) Integer[ ] sort duration: 101
2) Integer[ ] PARALLEL sort duration: 56
2) int[ ] sort duration: 33
3) ArrayList<Integer> sort duration: 124
3) Integer[ ] sort duration: 118
3) Integer[ ] PARALLEL sort duration: 96
3) int[ ] sort duration: 42
4) ArrayList<Integer> sort duration: 108
4) Integer[ ] sort duration: 102
4) Integer[ ] PARALLEL sort duration: 92
4) int[ ] sort duration: 57
5) ArrayList<Integer> sort duration: 142
5) Integer[ ] sort duration: 113
5) Integer[ ] PARALLEL sort duration: 118
5) int[ ] sort duration: 31
6) ArrayList<Integer> sort duration: 113
6) Integer[ ] sort duration: 103
6) Integer[ ] PARALLEL sort duration: 58
6) int[ ] sort duration: 32
7) ArrayList<Integer> sort duration: 115
7) Integer[ ] sort duration: 116
7) Integer[ ] PARALLEL sort duration: 57
7) int[ ] sort duration: 33
8) ArrayList<Integer> sort duration: 115
8) Integer[ ] sort duration: 115
8) Integer[ ] PARALLEL sort duration: 58
8) int[ ] sort duration: 31
9) ArrayList<Integer> sort duration: 114
9) Integer[ ] sort duration: 101
9) Integer[ ] PARALLEL sort duration: 52
9) int[ ] sort duration: 32
10) ArrayList<Integer> sort duration: 113
10) Integer[ ] sort duration: 114
10) Integer[ ] PARALLEL sort duration: 57
10) int[ ] sort duration: 32

EDIT: Added functionality to sort a Integer array.
EDIT: Added functionality to sort a Integer array using Parallel sort.

• David.Ren: I think, we need to ensure that, all the measurement base on same algorithm/method. Finally, intList.sort(null) invoke ComparableTimSort.sort(), Arrays.sort(intArray) invoke DualPivotQuicksort.sort()
• prasad_: The List can be sorted using parallel stream. There is no parallel stream option for arrays, just a parallel sort.