Быстрая сортировка массива байт в Java

Для текущих задач потребовалось сортировать большие массивы байт, как знаковых (signed), так и беззнаковых (unsigned). Размер массива в моем случае был около 10 мегабайт, это не так уж и много, то есть, можно использовать сортировку в памяти.

Поначалу стал использовать java.util.Arrays.sort(byte[])… К сожалению, это решение оказалось неприемлемым, так как:
— Arrays.sort позволяет сортировать только signed значения… весьма странно что разработчики JDK этим ограничились;
— Arrays.sort использует универсальный метод (подтюненный qsort), но для ряда задач, как например для текущей, это не оптимально.

В результате обратил внимание на так называемую сортировку подсчетом, которая в данном случае будет оптимальной. Реализация также получилась весьма простой.

Пояснение по поводу метода сортировки:

1. Инициализируем модель, которая представляет собой массив int[256]. Каждый i-й элемент модели является Ni (количество элементов исходного массива, равных i).

2. Заполняем результирующий массив, при этом последовательно записывая в него каждый i-й элемент модели Ni раз.

Все, этого достаточно, произведена очень быстрая сортировка в один проход!
Причем этот метод работает как для знаковой, так и для беззнаковой сортировки, разница лишь в том, что для беззнаковой заполнение результирующего массива ведется элементами в диапазоне от 0 до 255, а для знаковой — в диапазоне от -128 до 127.

Вот код класса (комменты удалил, чтобы занимало меньше места, для понимания принципа этого кода достаточно):

1. public class ByteArraySorter {
2.     private static final int BYTE_MODEL_SIZE = 256;
3.     private static final int BYTE_MASK = 0xFF;
4.     private static final int BYTE_SIGNED_MIN_VALUE = -128;
5.     private static final int BYTE_SIGNED_MAX_VALUE = 127;
6.     private static final int BYTE_UNSIGNED_MIN_VALUE = 0;
7.     private static final int BYTE_UNSIGNED_MAX_VALUE = 255;
8.  
9.     public static void sort(byte[] buffer) {
10.         sort(buffer, BYTE_SIGNED_MIN_VALUE, BYTE_SIGNED_MAX_VALUE);
11.     }
12.  
13.     public static void sortUnsigned(byte[] buffer) {
14.         sort(buffer, BYTE_UNSIGNED_MIN_VALUE, BYTE_UNSIGNED_MAX_VALUE);
15.     }
16.  
17.     private static void sort(byte[] buffer, int fromValue, int toValue) {
18.         if (buffer == null) { return; }
19.  
20.         int length = buffer.length;
21.         if (length == 0) { return; }
22.  
23.         int[] model = new int[BYTE_MODEL_SIZE];
24.  
25.         for (int i = 0; i < length; i++) {
26.             model[buffer[i] & BYTE_MASK]++;
27.         }
28.  
29.         int index = 0;
30.  
31.         for (int i = fromValue; i <= toValue; i++) {
32.             int toIndex = index + model[i & BYTE_MASK];
33.  
34.             while (index < toIndex) {
35.                 buffer[index] = (byte)i;
36.                 index++;
37.             }
38.         }
39.     }
40. }

* This source code was highlighted with Source Code Highlighter.

Результаты измерений для массива 10 мегабайт:

Arrays.sort(byte[]):
— массив, заполненный случайными значениями: 0.703 сек
— массив, заполненный уже отсортированными значениями: 0.231 сек
— массив, заполненный только нолями: 0.060 сек

ByteArraySort.sort(byte[]):
— массив, заполненный случайными значениями: 0.032 сек
— массив, заполненный уже отсортированными значениями: 0. 032 сек
— массив, заполненный только нолями: 0.047 сек

Каждый тест запускался 100 раз, взято минимальное значение (среднее отличается от минимального лишь на несколько миллисекунд, так что погрешностью в данном случае можно пренебречь).

Выгода сортировки подсчетом видна однозначно.

Примечание 1. Данный тип сортировки неэффективен для небольших массивов, то есть, если нужно отсортировать, скажем, менее чем 1000 элементов (значение 1000 получено экспериментально, но если у кого есть время и желание можно рассчитать математически, более точно), то лучше использовать другие виды сортировки. Если же массив содержит более 1000 элементов, то конкурентов у сортировки подсчетом практически нет.

Примечание 2. Данный алгоритм использует дополнительную память для модели, а именно 256 * 4 = 1024 байт. Хоть это и совсем немного, но все равно потенциально есть возможность получать OutOfMemoryError, это желательно учитывать.

Если кто предложит более оптимальный вариант, скажет что можно улучшить, или укажет на возможные недостатки, буду очень благодарен.