Случайно наткнулся на статью на java.dzone.com – Fast O(n) Integer Sorting Algorithm!

Всегда считал что O(n*log(n) ) это очень хороший показатель.  Например, стандартная реализация сортировки в Java 6 является слегка модифицированным вариантом merge sort, которая  соответственно дает время n*log(n).  Получить ультра ускорялку сортировки можно используя дополнительные хитрости: используя дополнительные знания о самих объектах которые мы сортируем + ограничения на возможные их значения.

Если верить википедии Гарольд Сьюард (Harold H. Seward) в 1954 году из MIT изобрел ультра крутой способ сортировки  – radix sort (поразрядная сортировка), а также разработал counting sort (сортировка подсчетом).
При такой сортировки мы не используем Comparator, т.е. сравнение и перестановка элементов как в обычной сортировки не происходит. С другой стороны, такой метод требует дополнительной памяти и
особо эффективен в тех случаях, когда мы сортируем большое количество натуральных чисел ограниченных по возможным принимаемым значениям. Например: массив из 1000000 целых чисел, которые принимают значения от 0 до 1000.

В исходной статье дается детальный график показывающий эффективность использования такой сортировки.

Далее привожу реализацию на Java алгоритм этой волшебной сортировки с моими комментариями.
Внимание! Такая сортировка работает для ПОЛОЖИТЕЛЬНЫХ int‘-ов.
Детальное описание алгоритма можно найти на википедии или нагуглить.
P.S.: У меня простое сравнение двух алгоритмов – через Arrays.sort() vs CountingSort.sort() дает выигрыш в пользу последнего (приблизительно в четыре раза быстрее на этом примере).

import java.util.Arrays;
import java.util.Random;

public class CountingSort {

    /**
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        int min, max = min = array[0];
        // тупо находим максимальное и минимальное значение
        for (int i = 1; i < array.length; i++) {
            if (array[i] < min) {
                   min = array[i];
            }
            if (array[i] > max) {
                max = array[i];
            }
        }
        // понеслась
        return sort(array, min, max);
    }

    static int[] sort(int[] array, int min, int max) {
        // счетчик это такой массив в котором мы будем считать, как часто встречаются
        // числа в сортируемом массиве.
        // допустим массив равен = {0,2,1,5,1}, min = 0, max = 5
        // счетчик = count[0]....count[5]
        int[] count = new int[max - min + 1];
        // итак считаем...
        for (int i = 0; i < array.length; i++) {
            // подсчитываем сколько раз встречается число,
            // встретилось +1 к счетчику
            count[array[i] - min]++;
        }
        // например. count[0]=1, count[1]=2, count[3]=0,count[4]=0,count[5]=1
        int idx = 0;
        // теперь все готово
        // пробегаем по всему счетчику (от 0 до 5)
        // count[i] - показывает сколько раз встречается то или иное число
        for (int i = 0; i < count.length; i++) {
            // count[0]=1, значит array[0]=0;
            // count[1]=2, значит вставляем два раза array[1]=array[2]=1;
            // count[2]=1, опять только один раз. array[3]=2;
            // count[3]=0, значит ничего не вставляем и т.д.
            for (int j = 0; j < count[i]; j++) {
                array[idx++] = i + min;
            }
        }
        // ну собственно и всё
        return array;
    }

    public static void main(String[] args) {
        Random rnd = new Random();
        int arr1[] = new int[1024*1024];
        for (int i = 0; i < arr1.length; ++i) {
            arr1[i] = rnd.nextInt(1000) + 123;
        }
        int arr2[] = new int[arr1.length];
        System.arraycopy(arr1, 0, arr2, 0, arr1.length);
        long t1 = System.currentTimeMillis();
        sort(arr1);
        long t2 = System.currentTimeMillis();
        Arrays.sort(arr2);
        long t3 = System.currentTimeMillis();
        System.out.printf("counting sort: %d merge sort: %d \r\n", (t2-t1), (t3-t2));
        //
        System.out.println(Arrays.equals(arr1, arr2));
    }
}