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 
