I was curious, how in-place radix sort compares to the variant which uses an auxiliary array in order to speed up the sorting. I implemented both and tested it against java.util.Arrays.sort(int[]).Seed: 1439451337582Radixsort.InPlace.sort in 12074 milliseconds.Radixsort.sort in 6937 milliseconds.Arrays.sort in 16316 milliseconds.Arrays identical: trueWhat do you think?Radixsort.java:package net.coderodde.util;import java.util.Arrays;/** * This class implements a radix sort using an auxiliary array in order to speed * up sorting. *  * @author Rodion rodde Efremov * @version 1.6 */public class Radixsort {    /**     * The byte index of the most significant byte in each 32-bit integer.     */    private static final int MOST_SIGNIFICANT_BYTE_INDEX = 3;    /**     * The mask for manipulating the sign bit.     */    private static final int SIGN_BIT_MASK = 0x8000_0000;    /**     * The amount of bits per byte.     */    private static final int BITS_PER_BYTE = 8;    /**     * The mask for extracting the bucket index.     */    private static final int EXTRACT_BYTE_MASK = 0xff;    /**     * The amount of buckets considered for sorting.     */    private static final int BUCKET_AMOUNT = 256;    /**     * If the range length is less than this constant use      * {@link java.util.Arrays.sort} and exit.     */    private static final int QUICKSORT_THRESHOLD = 128;    /**     * This inner static class provides an in-place implementation of the radix     * sort.     */    public static final class InPlace {        /**         * Sorts the range {@code array[fromIndex], array[fromIndex + 1], ...,         * array[toIndex - 2], array[toIndex - 1]}.         *          * @param array     the array holding the target range.         * @param fromIndex the starting, inclusive index of the range.         * @param toIndex   the ending, exclusive index of the range.         */        public static void sort(int[] array, int fromIndex, int toIndex) {            if (toIndex - fromIndex < 2) {                return;            }            sort(array, fromIndex, toIndex, MOST_SIGNIFICANT_BYTE_INDEX);        }        /**         * Sorts the entire array.         *          * @param array the array to sort.         */        public static void sort(int[] array) {            sort(array, 0, array.length);        }        private static void sort(int[] array,                                  int fromIndex,                                 int toIndex,                                 int byteIndex) {            if (toIndex - fromIndex < QUICKSORT_THRESHOLD) {                Arrays.sort(array, fromIndex, toIndex);                return;            }            int[] bucketSizeMap = new int[BUCKET_AMOUNT];            // Count the size of each bucket.            for (int i = fromIndex; i < toIndex; ++i) {                bucketSizeMap[getBucketIndex(array[i], byteIndex)]++;            }            // Compute the map mapping each bucket into its start index.            int[] startIndexMap = new int[BUCKET_AMOUNT];            startIndexMap[0] = fromIndex;            for (int i = 1; i < BUCKET_AMOUNT; ++i) {                startIndexMap[i] = startIndexMap[i - 1] + bucketSizeMap[i - 1];            }            int[] processedMap = new int[BUCKET_AMOUNT];            boolean[] bucketReadyMap = new boolean[BUCKET_AMOUNT];            // Now move the elements to their proper buckets.            for (int index = fromIndex; index < toIndex;) {                int element = array[index];                int elementBucketIndex = getBucketIndex(element, byteIndex);                int targetIndex = startIndexMap[elementBucketIndex] +                                   processedMap[elementBucketIndex];                if (bucketReadyMap[elementBucketIndex]                         || index == targetIndex) {                    ++index;                } else {                    int tmp = array[targetIndex];                    array[targetIndex] = element;                    array[index] = tmp;                    processedMap[elementBucketIndex]++;                }                if (processedMap[elementBucketIndex]                         == bucketSizeMap[elementBucketIndex]) {                    bucketReadyMap[elementBucketIndex] = true;                }            }            // Recur to sorting the buckets.            if (byteIndex > 0) {                // If more bytes are available, recursively sort the buckets.                for (int i = 0; i < BUCKET_AMOUNT; ++i) {                    if (bucketSizeMap[i] != 0) {                        sort(array,                              startIndexMap[i],                             startIndexMap[i] + bucketSizeMap[i],                             byteIndex - 1);                    }                }            }        }    }    /**     * Sorts the range {@code array[fromIndex], array[fromIndex + 1], ...,     * array[toIndex - 2], array[toIndex - 1]}.     *      * @param array     the array holding the target range.     * @param fromIndex the starting, inclusive index of the range.     * @param toIndex   the ending, exclusive index of the range.     */    public static void sort(int[] array, int fromIndex, int toIndex) {        if (toIndex - fromIndex < 2) {            return;        }        sort(array,             Arrays.copyOfRange(array, fromIndex, toIndex),              fromIndex,             0,             toIndex - fromIndex,             MOST_SIGNIFICANT_BYTE_INDEX);    }    /**     * Sorts the entire array.     *      * @param array the array to sort.     */    public static void sort(int[] array) {        sort(array, 0, array.length);    }    private static void sort(int[] source,                              int[] target,                             int sourceOffset,                             int targetOffset,                             int rangeLength,                             int byteIndex) {        if (rangeLength < QUICKSORT_THRESHOLD) {            Arrays.sort(source, sourceOffset, sourceOffset + rangeLength);            if ((byteIndex & 1) == 0) {                System.arraycopy(source,                                  sourceOffset,                                  target,                                  targetOffset,                                  rangeLength);            }            return;        }        int[] bucketSizeMap = new int[BUCKET_AMOUNT];        // Count the size of each bucket.        for (int i = sourceOffset; i < sourceOffset + rangeLength; ++i) {            bucketSizeMap[getBucketIndex(source[i], byteIndex)]++;        }        // Compute the map mapping each bucket to its beginning index.        int[] startIndexMap = new int[BUCKET_AMOUNT];        for (int i = 1; i < BUCKET_AMOUNT; ++i) {            startIndexMap[i] = startIndexMap[i - 1] + bucketSizeMap[i - 1];        }        // The map mapping each bucket index to amount of elements already put        // in the bucket.        int[] processedMap = new int[BUCKET_AMOUNT];        for (int i = sourceOffset; i < sourceOffset + rangeLength; ++i) {            int element = source[i];            int bucket = getBucketIndex(element, byteIndex);            target[targetOffset + startIndexMap[bucket] +                                    processedMap[bucket]++] = element;        }        if (byteIndex > 0) {            // Recursively sort the buckets.            for (int i = 0; i < BUCKET_AMOUNT; ++i) {                if (bucketSizeMap[i] != 0) {                    sort(target,                          source,                          targetOffset + startIndexMap[i],                         sourceOffset + startIndexMap[i],                          bucketSizeMap[i],                          byteIndex - 1);                }            }        }    }    /**     * Returns the bucket index for {@code element} when considering      * {@code byteIndex}th byte within the element. The indexing starts from     * the least significant bytes.     *      * @param element   the element for which to compute the bucket index.     * @param byteIndex the index of the byte to be considered.     * @return the bucket index.     */    private static int getBucketIndex(int element, int byteIndex) {        return ((byteIndex == MOST_SIGNIFICANT_BYTE_INDEX ?                  element ^ SIGN_BIT_MASK :                 element) >>> (byteIndex * BITS_PER_BYTE)) & EXTRACT_BYTE_MASK;    }}Demo.java:import java.util.Arrays;import java.util.Random;import java.util.stream.IntStream;import net.coderodde.util.Radixsort;/** * This class implements a demonstration comparing the performance of the radix * sorts. *  * @author Rodion rodde Efremov * @version 1.6 */public class Demo {    public static void main(String[] args) {        long seed = System.currentTimeMillis();        Random random = new Random(seed);        int[] array1 = getRandomIntegerArray(100000000, random);        int[] array2 = array1.clone();        int[] array3 = array1.clone();        System.out.println(Seed:  + seed);        long startTime = System.currentTimeMillis();        Radixsort.InPlace.sort(array1, 3, array1.length - 4);        long endTime = System.currentTimeMillis();        System.out.println(Radixsort.InPlace.sort in  + (endTime - startTime) +                             milliseconds.);        startTime = System.currentTimeMillis();        Radixsort.sort(array2, 3, array2.length - 4);        endTime = System.currentTimeMillis();        System.out.println(Radixsort.sort in  + (endTime - startTime) +                            milliseconds.);        startTime = System.currentTimeMillis();        Arrays.sort(array3, 3, array2.length - 4);        endTime = System.currentTimeMillis();        System.out.println(Arrays.sort in  + (endTime - startTime) +                             milliseconds.);        System.out.println(Arrays identical:  +                 (Arrays.equals(array1, array2) &&                  Arrays.equals(array2, array3)));    }    private static int[] getRandomIntegerArray(int size, Random random) {        return IntStream.range(0, size).map((a) -> random.nextInt()).toArray();    }}
Radix sorts in Java
java;algorithm;sorting;radix sort