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

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