Gist for net.coderodde.util.Arrays.sort(byte[])

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 array the array to sort.
     */
    public static void sort(byte[] array) {
        sort(array, 0, array.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(LENGTH1);
        benchmark(LENGTH1);
        benchmark(LENGTH2);
        benchmark(LENGTH3);
        benchmark(LENGTH4);
    }
    
    private static final int LENGTH1 = 100_000_000;
    private static final int LENGTH2 = 10_000_000;
    private static final int LENGTH3 = 1_000_000;
    private static final int LENGTH4 = 100_000;
    
    private static final void warmup(int length) {
        runBenchmark(false, length);
    }
    
    private static final void benchmark(int length) {
        runBenchmark(true, length);
    }
    
    private static final void runBenchmark(boolean output, int length) {
        if (output) {
            System.out.println("=== Length: " + length + " ===");
        }
            
        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("--- Random array ---");
            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();
        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)));
            System.out.println();
        }
        
        array1 = createEqualElementByteArray(length);
        array2 = array1.clone();
        array3 = array1.clone();
        
        startTime = System.nanoTime();
        java.util.Arrays.sort(array1);
        endTime = System.nanoTime();
        
        if (output) {
            System.out.println("--- Equal element array ---");
            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();
        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)));
            
            System.out.println();
            System.out.println();
        }
    }
    
    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;
    }
    
    private static final byte[] createEqualElementByteArray(int length) {
        byte[] array = new byte[length];
        
        for (int i = 0; i < length; i++) {
            array[i] = -1;
        }
        
        return array;
    }
}