Почему сортировка Java превосходит сортировку подсчета для примитивов

Question

Я сравниваю время выполнения сортировки Counting с Java native Arrays.sort. Из того, что я прочитал, сортировка «Подсчет» предлагает лучшее, среднее и худшее время выполнения n + k. Примитивы типа Javas Arrays, использующие двойную сводную сортировку, представляют собой алгоритм, основанный на сравнении, поэтому должны предлагать O (n log n) в среднем случае и наихудший вариант On2.

При сравнении двух данных путем измерения времени (наносекунд), необходимого для сортировки серии массивов размером от 500 до 100 КБ, я отметил резкое увеличение времени выполнения для сортировки Подсчет, когда размер достиг ~ 70 КБ.

Насколько я понимаю, сортировка «Подсчет» эффективна, если диапазон входных данных не намного больше количества сортируемых элементов. Массивы построены из случайных чисел от 0 до 99, поэтому k всегда будет быть намного меньше, чем n.

Будет ли какая-то конкретная причина, по которой сортировка счетчиков будет вырождаться так резко с ростом n?

Моя реализация сортировки подсчета:

public static int[] countSort(int[] arr, int k) {
        /*
         * This will only work on positive integers 0 to K.
         * For negative  worst case testing we use the negative count sort below.
         * 
         * Step 1: Use an array to store the frequency of each element. For array
         * elements 1 to K initialize an array with size K. Step 2: Add elements of
         * count array so each element stores summation of its previous elements. Step
         * 3: The modified count array stores the position of elements in actual sorted
         * array. Step 5: Iterate over array and position elements in correct position
         * based on modified count array and reduce count by 1.
         */

        int[] result = new int[arr.length];
        int[] count = new int[k + 1];
        for (int x = 0; x < arr.length; x++) {
            count[arr[x]]++;
        }

        /*
         * Store count of each element in the count array Count[y] holds the number of
         * values of y in the array 'arr'
         */

        for (int y = 1; y <= k; y++) {
            count[y] += count[y - 1];
        }

        /*
         * Change count[i] so that count[i] now contains actual Position of this element
         * in result array
         */

        for (int i = arr.length - 1; i >= 0; i--) {
            result[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }

        System.out.println("COUNTSORT SORTED ARRAY = " + Arrays.toString(result));
        return result;

    }

Разрешение: Запуск сортировки подсчета на месте в соответствии с предложением @ Alex привел к намного более высокому времени выполнения.

Answer 1

Просто предположение, но ваш алгоритм сортировки использует гораздо больше памяти, чем Java. 70 КБ - 280 КБ. Вам нужно удвоить пространство, более 512 КБ. В зависимости от используемого процессора, это может иметь значение между запуском сортировки в (L1?) И большим количеством ошибок в кеше. Поскольку вам не нужна копия, выполните сортировку на месте. Если теперь вы попали в стену позже, у вас есть ответ.

Редактировать: это 280 КБ.

Редактировать2: вчера было поздно, так что вот идет версия на месте. Обратите внимание, что он изменяет входной массив.

public static int[] countSortRefactored(int[] arr, int k) {
    int[] count = new int[k + 1];
    for (int x = 0; x < arr.length; x++) {
        count[arr[x]]++;
    }

    int idx=0;
    for (int x=0; x<=k; x++) {
        Arrays.fill(arr, idx, idx+=count[x], x);
    }

    System.out.println("COUNTSORT SORTED ARRAY = " + Arrays.toString(arr));
    return arr;
}