Сортировка подсчётом

Сортировка без сравнений между элементами

Сортировка подсчётом подходит к задаче иначе: вместо вопроса «какой из двух элементов меньше?» она считает, сколько раз встретилось каждое значение. Это возможно, когда значения — целые числа из достаточно небольшого известного диапазона.

static void countingSort(int[] a, int maxValue) {
    int[] count = new int[maxValue + 1];

    for (int value : a) {
        count[value]++;
    }

    int index = 0;
    for (int value = 0; value < count.length; value++) {
        for (int c = 0; c < count[value]; c++) {
            a[index++] = value;
        }
    }
}

Массив count хранит частоты. Если count[4] == 3, значение 4 нужно записать в результат три раза. Проход по счётчикам идёт от меньшего индекса к большему, поэтому итоговый массив автоматически получается отсортированным.

Сложность зависит от диапазона

Пусть n — число элементов, а k — размер диапазона возможных значений. Тогда время работы составляет O(n + k), а дополнительная память — O(k). При небольшом k это может быть быстрее сравнительных сортировок.

Когда идея перестаёт быть выгодной

Если в массиве всего несколько элементов, но возможные значения растянуты от нуля до миллиардов, создавать гигантский массив счётчиков бессмысленно. Counting sort выигрывает именно тогда, когда диапазон значений достаточно компактен относительно объёма данных.