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

Possible duplicate of [Collections vs Arrays regarding sort()](https://stackoverflow.com/questions/5208133/collections-vs-arrays-regarding-sort) — Kaustubh Khare, Jul 19 '18 at 05:47
`List` 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. — prasad_, Jul 19 '18 at 06:04
How many times had you tried? I have tested on my machine with ```ArrayList``` and ```Integer[]```, they are almost the same time. — zhh, Jul 19 '18 at 06:06
[How do I write a correct microbenchmark in Java](https://stackoverflow.com/q/504103/3788176) — Andy Turner, Jul 19 '18 at 06:26
@prasad, I simplified my problem from a bigger project. So you can consider that I have a kind of object, and the object contains int field which can be sort. — David.Ren, Jul 19 '18 at 06:38

score 2 · Accepted Answer · edited Jun 20 '20 at 09:12

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

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 — astafev.evgeny, Jul 19 '18 at 07:09
JIT and other Java optimization techniques make it very hard to correctly setup micro-benchmark. — Jerry Chin, Jul 19 '18 at 08:00

zhh · Answer 2 · 2018-07-19T06:20:56.023

1

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

edited Jul 19 '18 at 06:20

answered Jul 19 '18 at 06:12

zhh

2,346
1
11
22

1

I have run your code , b-a=446, c-d=91. My Java version is 8. Which is yours? – David.Ren Jul 19 '18 at 06:22
@David.Ren I got both 220~240, My java version is 7. – zhh Jul 19 '18 at 06:24

prasad_ · Answer 3 · 2018-07-19T07:30:09.967

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.

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() — David.Ren, Jul 19 '18 at 07:43
The `List` can be sorted using parallel stream. There is no parallel stream option for arrays, just a parallel sort. — prasad_, Jul 19 '18 at 07:57

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

3 Answers3