I have this counting sort for byte values running in linear time with respect to array length:
Arrays.java
package net.coderodde.util;
import java.util.Random;
/**
* This class contains static methods for sorting {@code byte} arrays.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Apr 24, 2019)
*/
public final class Arrays {
/**
* Sorts the given {@code byte} array in its entirety.
*
* @param arrays the array to sort.
*/
public static void sort(byte[] arrays) {
sort(arrays, 0, arrays.length);
}
/**
* Sorts the given {@code byte} array omitting first {@code fromIndex}
* array components starting from beginning, and omitting last
* {@code array.length - toIndex} array components from the ending.
*
* @param array the array holding the target range.
* @param fromIndex the starting index of the target range.
* @param toIndex one position to the right from the last element
* belonging to the target range.
*/
public static void sort(byte[] array, int fromIndex, int toIndex) {
rangeCheck(array.length, fromIndex, toIndex);
int[] bucketCounters = new int[256];
for (int index = fromIndex; index < toIndex; index++) {
bucketCounters[Byte.toUnsignedInt(array[index])]++;
}
int index = fromIndex;
// Insert the negative values first:
for (int bucketIndex = 128; bucketIndex != 256; bucketIndex++) {
java.util.Arrays.fill(array,
index,
index += bucketCounters[bucketIndex],
(byte) bucketIndex);
}
// Insert the positive values next:
for (int bucketIndex = 0; bucketIndex != 128; bucketIndex++) {
java.util.Arrays.fill(array,
index,
index += bucketCounters[bucketIndex],
(byte) bucketIndex);
}
}
/**
* Checks that {@code fromIndex} and {@code toIndex} are in
* the range and throws an exception if they aren't.
*/
private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
if (fromIndex > toIndex) {
throw new IllegalArgumentException(
"fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
}
if (fromIndex < 0) {
throw new ArrayIndexOutOfBoundsException(fromIndex);
}
if (toIndex > arrayLength) {
throw new ArrayIndexOutOfBoundsException(toIndex);
}
}
public static void main(String[] args) {
warmup();
benchmark();
}
private static final int LENGTH = 50_000_000;
private static final void warmup() {
runBenchmark(false);
}
private static final void benchmark() {
runBenchmark(true);
}
private static final void runBenchmark(boolean output) {
long seed = System.currentTimeMillis();
Random random = new Random();
byte[] array1 = createRandomByteArray(LENGTH, random);
byte[] array2 = array1.clone();
byte[] array3 = array1.clone();
if (output) {
System.out.println("seed = " + seed);
}
long startTime = System.nanoTime();
java.util.Arrays.sort(array1);
long endTime = System.nanoTime();
if (output) {
System.out.println("java.util.Arrays.sort(byte[]) in " +
(endTime - startTime) / 1e6 +
" milliseconds.");
}
startTime = System.nanoTime();
java.util.Arrays.parallelSort(array2);
endTime = System.nanoTime();
if (output) {
System.out.println("java.util.Arrays.parallelSort(byte[]) in " +
(endTime - startTime) / 1e6 +
" milliseconds.");
}
startTime = System.nanoTime();
net.coderodde.util.Arrays.sort(array3);
endTime = System.nanoTime();
if (output) {
System.out.println("net.coderodde.Arrays.sort(byte[]) in " +
(endTime - startTime) / 1e6 +
" milliseconds.");
System.out.println("Algorithms agree: " +
(java.util.Arrays.equals(array1, array2) &&
java.util.Arrays.equals(array1, array3)));
}
}
private static final byte[] createRandomByteArray(int length,
Random random) {
byte[] array = new byte[length];
for (int i = 0; i < length; i++) {
array[i] = (byte) random.nextInt();
}
return array;
}
}
Typical output
seed = 1556112137029
java.util.Arrays.sort(byte[]) in 67.6446 milliseconds.
java.util.Arrays.parallelSort(byte[]) in 210.0057 milliseconds.
net.coderodde.Arrays.sort(byte[]) in 46.6332 milliseconds.
Algorithms agree: true