Comparing Arrays.sort() and Collections.sort()

[Andrzej Borucki]

Time difference between Arrays.sort() and Collections.sort( ) is enormous, why?

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

public class Main {
    public static double log2(double x) {
        return Math.log(x) / Math.log(2);
    }
    
    public static void main(String[] args) {
        Random rand = new Random();
        int minMeasureTime = 1_000_000_000;
        int[] sizes = {1_000, 2_000, 5_000,
                10_000, 20_000, 50_000,
                100_000, 200_000, 500_000,
                1_000_000, 2_000_000, 5_000_000};
        long sum = 0;
        for (int size : sizes) {
            System.out.printf("%nsize %d%n", size);
            long best1 = Long.MAX_VALUE;
            long measureTime = 0;
            int nTrials = 0;
            do {
                int[] numbers = new int[size];
                for (int i = 0; i < size; i++) {
                    numbers[i] = rand.nextInt();
                }
                long startTime1 = System.nanoTime();
                Arrays.sort(numbers);
                long endTime1 = System.nanoTime();
                long sortTime1 = endTime1 - startTime1;
                if (sortTime1 < best1) best1 = sortTime1;
                measureTime += sortTime1;
                for (int i = 0; i < size; i++) {
                    sum += i + numbers[i];
                }
                nTrials++;
            } while ( measureTime < minMeasureTime);
            double avg1 = (double) measureTime / nTrials;
            System.out.printf("array sort time %f ms%n", (double) avg1 / 1e6);
            System.out.printf("array sort time/size/log2(size) %f ns%n", (double) avg1/size/log2(size));

            long best2 = Long.MAX_VALUE;
            measureTime = 0;
            nTrials = 0;
            do {
                ArrayList<Integer> numbers = new ArrayList<>();
                for (int i = 0; i < size; i++) {
                    numbers.add(rand.nextInt());
                }
                long startTime2 = System.nanoTime();
                Collections.sort(numbers);
                long endTime2 = System.nanoTime();
                long sortTime2 = endTime2 - startTime2;
                if (sortTime2 < best2) best2 = sortTime2;
                measureTime += sortTime2;
                for (int i = 0; i < size; i++) {
                    sum += i + numbers.get(i);
                }
                nTrials++;
            } while ( measureTime < minMeasureTime);
            double avg2 = (double) measureTime / nTrials;
            System.out.printf("list sort time %f ms%n", (double) avg2 / 1e6);
            System.out.printf("list sort time/size/log2(size) %f ns%n", (double) avg2/size/log2(size));

            System.out.printf("arrays speedup = %f times%n", avg2 / avg1);
        }
        System.out.printf("%n%n%d%n" , sum % 2);
    }
}

size 1000000
array sort time 12.797650 ms
array sort time/size/log2(size) 0.642079 ns
list sort time 461.183508 ms
list sort time/size/log2(size) 23.138345 ns
arrays speedup = 36.036578 times

size 2000000
array sort time 26.375102 ms
array sort time/size/log2(size) 0.630032 ns
list sort time 857.165750 ms
list sort time/size/log2(size) 20.475430 ns
arrays speedup = 32.499049 times

size 5000000
array sort time 74.852897 ms
array sort time/size/log2(size) 0.672729 ns
list sort time 2582.375501 ms
list sort time/size/log2(size) 23.208717 ns
arrays speedup = 34.499339 times

[Rob Spoor]

You're comparing apples and oranges. There's already quite some overhead when using Integer instead of int because of auto-unboxing. If I change the int[] into an Integer[] the array speedup is around 1, sometimes even less than 1 meaning they have equivalent performances.

Before Java 8 the list sorting would have been worse though, because Collections.sort always called list.toArray() first. It now delegates to list.sort(null) which by default calls this.toArray() but ArrayList has overridden it to directly delegate to Arrays.sort.