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();
}
}
InPlace.sort(int[])? \$\endgroup\$ints are not objects. \$\endgroup\$