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

Answer 2

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

Answer 3

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);