Radix sorts in Java

Question

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: 1439451337582
Radixsort.InPlace.sort in 12074 milliseconds.
Radixsort.sort in 6937 milliseconds.
Arrays.sort in 16316 milliseconds.
Arrays identical: true

What 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();
 }
}

• JS1: I would have thought the out-of-place sort would use a LSB algorithm, which would be faster than the MSB algorithm.
• Jan: In order to qualify the inPlace vs outPlace, we would need to evaluate the memory costs :) Repeat the tests with hundreds of arrays of various sizes, so that the garbage collector start hurting. Then compare :)
• greybeard: Care to include a statement about the stability of InPlace.sort(int[])?
• coderodde: @greybeard Not relevant since ints are not objects.

Answer 1

Not much to say about this lovely well-documented code, it's very well written. Just some notes:

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;
}

The return statement looks ugly and hard to read. Turn it into an if statement:

private static int getBucketIndex(int element, int byteIndex) {
 int result = element;
 if (byteIndex == MOST_SIGNIFICANT_BYTE_INDEX) {
 result ^= SIGN_BIT_MASK;
 }
 return (result >>> (byteIndex * BITS_PER_BYTE)) & EXTRACT_BYTE_MASK;
}