sort(); java , 100 элементов сортирует быстрее чем 10

#java

sort(); java , 100 элементов сортирует быстрее чем 10 почему так ?

 Random random = new Random();
    int[] array10 = new int[10];
    int[] array100 = new int[100];
    int[] array1000 = new int[1000];

    for (int i = 0; i < array10.length; i++) {
        array10[i]=random.nextInt(10000);
    }
    for (int i = 0; i < array100.length; i++) {
        array100[i]=random.nextInt(10000);
    }
    for (int i = 0; i < array1000.length; i++) {
        array1000[i]=random.nextInt(10000);
    }

// быстрая сортировка
        long start0 = System.nanoTime();
        Arrays.sort(array10);
        long end0 = System.nanoTime();
        long traceTime0 = end0-start0;

    long start1 = System.nanoTime();
    Arrays.sort(array100);
    long end1 = System.nanoTime();
    long traceTime1 = end1-start1;

    long start2 = System.nanoTime();
    Arrays.sort(array1000);
    long end2 = System.nanoTime();
    long traceTime2 = end2-start2;

    // в наносекундах
    System.out.println("Qsort");
    System.out.println("10 elements: " + traceTime0+"ns");
    System.out.println("100 elements: " +traceTime1+"ns");
    System.out.println("1000 elements: " +traceTime2+"ns");


Консоль: 

Qsort
10 elements: 974322ns
100 elements: 80737ns
1000 elements: 1101587ns

    

Ответы

Ответ 1

У вас неверная методика замера времени работы алгоритма. Попробуйте запустить сортировку
меньшего массива последней, она станет заметно быстрее остальных: https://repl.it/repls/WordyLightgrayIntegers.

Вы замеряете всего один прогон алгоритма. В такой ситуации на результат замеров тут
может влиять множество факторов - от "прогрева" JIT-компилятора и накладных расходов
на загрузку класса Arrays  до случайных всплесков использования CPU другими программами.
Сделайте хотя бы 10000 прогонов для каждого массива и возьмите среднее время - результат
будет более точным. Также можете сделать ручной "прогрев" – несколько раз отсортировать
массивы вхолостую, и только после этого приступать к замерам.

Ну и на десерт – если посмотреть на реализацию сортировки в методе Arrays.sort(),
то можно увидеть, что для небольших массивов (до 286 элементов) используется алгоритм
QuickSort, а для совсем маленьких (до 47 элементов) - сортировка вставками. У последней
сложность варьируется от линейной до квадратичной, в зависимости от того, насколько
отсортированы данные в исходном массиве. Это ещё один аргумент в пользу неточности
единичного замера.


Ответ 2

Обернул код в while(true)
получаю такие результаты. Полагаю дело может быть связано в отсутсвием прогрева при
замерах.

Qsort
10 elements: 367ns
100 elements: 2932ns
1000 elements: 39953ns


Вот ссылка на вопрос про прогрев JIT