Efficient counting sort for large byte arrays in Java

Question

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

Answer 1

I find the big points covered well:

• class and methods have one clear, documented purpose
• the API follows the well-known java.util.Arrays
  (if not to the point of documenting RuntimeExceptions thrown)

---

I'd try to get rid of magic literals and code replication:
size counts = new int[Byte.MAX_VALUE-Byte.MIN_VALUE+1] (or 1<<Byte.SIZE?), use

for (int bucket = Byte.MIN_VALUE ; bucket <= Byte.MAX_VALUE; bucket++)
    Arrays.fill(array,
                index, 
                index += counts[Byte.toUnsignedInt((byte) bucket)], 
                (byte) bucket);

I found it interesting to ogle the RTE source code I use.