This post elaborates on Efficient least-significant digit (LSD) radix sort for int keys in Java. This time, I made mild corrections to my code and provided the radix sort for long keys too.
Code
com.github.coderodde.util.LsdRadixsort.java:
package com.github.coderodde.util;
import java.util.Arrays;
/**
* This class provides the method for sorting {@code int} arrays using
* least-significant digit (LSD) radix sort.
*/
public final class LsdRadixsort {
/**
* The number of counters in the counter array.
*/
private static final int RADIX = 256;
private LsdRadixsort() {
}
/**
* Sorts the entire {@code int} array into ascending order.
*
* @param array the array to sort.
*/
public static void sort(int[] array) {
sort(array, 0, array.length);
}
/**
* Sorts the entire {@code long} array into ascending order.
*
* @param array the array to sort.
*/
public static void sort(long[] array) {
sort(array, 0, array.length);
}
/**
* Sorts the range {@code array[fromIndex ... toIndex - 1]} into ascending
* order.
*
* @param array the array holding the range.
* @param fromIndex the starting, inclusive index of the sorting range.
* @param toIndex the ending, exclusive index of the sorting range.
*/
public static void sort(int[] array, int fromIndex, int toIndex) {
checkRangeIndices(array.length,
fromIndex,
toIndex);
int rangeLength = toIndex - fromIndex;
if (rangeLength < 2) {
// Trivially sorted:
return;
}
// buffer and counterMap are allocated only once for the sake of
// performance:
int[] buffer = new int[rangeLength];
int[] counterMap = new int[RADIX];
sortImpl(array,
buffer,
counterMap,
fromIndex,
toIndex);
}
/**
* Sorts the range {@code array[fromIndex ... toIndex - 1]} into ascending
* order.
*
* @param array the array holding the range.
* @param fromIndex the starting, inclusive index of the sorting range.
* @param toIndex the ending, exclusive index of the sorting range.
*/
public static void sort(long[] array, int fromIndex, int toIndex) {
checkRangeIndices(array.length,
fromIndex,
toIndex);
int rangeLength = toIndex - fromIndex;
if (rangeLength < 2) {
// Trivially sorted:
return;
}
// buffer and counterMap are allocated only once for the sake of
// performance:
long[] buffer = new long[rangeLength];
int[] counterMap = new int[RADIX];
sortImpl(array,
buffer,
counterMap,
fromIndex,
toIndex);
}
/**
* Implements the actual sorting.
*
* @param array the array to sort.
* @param buffer the sorting buffer array.
* @param counterMap the bucket counter array.
* @param fromIndex the starting, inclusive index of the sorting range.
* @param toIndex the ending, exclsuive index of the sorting range.
*/
private static void sortImpl(int[] array,
int[] buffer,
int[] counterMap,
int fromIndex,
int toIndex) {
// Sort first by least-significant bytes, then by second
// least-significant, and finally by third least-signficant byte:
for (int byteIndex = 0; byteIndex < 3; byteIndex++) {
countingSortImpl(array,
buffer,
counterMap,
byteIndex,
fromIndex,
toIndex);
}
// Deal with the signed data:
countingSortImplSigned(array,
buffer,
counterMap,
fromIndex,
toIndex);
}
/**
* Implements the actual sorting.
*
* @param array the array to sort.
* @param buffer the sorting buffer array.
* @param counterMap the bucket counter array.
* @param fromIndex the starting, inclusive index of the sorting range.
* @param toIndex the ending, exclsuive index of the sorting range.
*/
private static void sortImpl(long[] array,
long[] buffer,
int[] counterMap,
int fromIndex,
int toIndex) {
// Sort first by least-significant bytes, then by second
// least-significant, and finally by third least-signficant byte:
for (int byteIndex = 0; byteIndex < 7; byteIndex++) {
countingSortImpl(array,
buffer,
counterMap,
byteIndex,
fromIndex,
toIndex);
}
// Deal with the signed data:
countingSortImplSigned(array,
buffer,
counterMap,
fromIndex,
toIndex);
}
/**
* Performs the counting sort on {@code array[fromIndex ... toIndex - 1]}.
*
* @param array the array to sort.
* @param buffer the buffer array.
* @param counterMap the counter array. We reuse this in order not to
* allocate it everytime we call this method.
* @param byteIndex the index of the byte that serves as the sorting key.
* @param fromIndex the starting, inclusive index of the sorting range.
* @param toIndex the ending, exclusive index of the sorting range.
*/
private static void countingSortImpl(int[] array,
int[] buffer,
int[] counterMap,
int byteIndex,
int fromIndex,
int toIndex) {
Arrays.fill(counterMap, 0);
// Count the elements:
for (int i = fromIndex; i != toIndex; i++) {
counterMap[extractCounterIndex(array[i], byteIndex)]++;
}
// Make the counter map accummulative:
for (int i = 1; i != RADIX; i++) {
counterMap[i] += counterMap[i - 1];
}
// Build the buffer array (which will end up sorted):
for (int i = toIndex - 1; i >= fromIndex; i--) {
int index = extractCounterIndex(array[i], byteIndex);
buffer[--counterMap[index]] = array[i];
}
// Just copy the buffer to the array:
System.arraycopy(buffer,
0,
array,
fromIndex,
buffer.length);
}
/**
* Performs the counting sort on {@code array[fromIndex ... toIndex - 1]}.
*
* @param array the array to sort.
* @param buffer the buffer array.
* @param counterMap the counter array. We reuse this in order not to
* allocate it everytime we call this method.
* @param byteIndex the index of the byte that serves as the sorting key.
* @param fromIndex the starting, inclusive index of the sorting range.
* @param toIndex the ending, exclusive index of the sorting range.
*/
private static void countingSortImpl(long[] array,
long[] buffer,
int[] counterMap,
int byteIndex,
int fromIndex,
int toIndex) {
Arrays.fill(counterMap, 0);
// Count the elements:
for (int i = fromIndex; i != toIndex; i++) {
counterMap[extractCounterIndex(array[i], byteIndex)]++;
}
// Make the counter map accummulative:
for (int i = 1; i != RADIX; i++) {
counterMap[i] += counterMap[i - 1];
}
// Build the buffer array (which will end up sorted):
for (int i = toIndex - 1; i >= fromIndex; i--) {
int index = extractCounterIndex(array[i], byteIndex);
buffer[--counterMap[index]] = array[i];
}
// Just copy the buffer to the array:
System.arraycopy(buffer,
0,
array,
fromIndex,
buffer.length);
}
/**
* Sorts the {@code array[fromIndex ... toIndex - 1]} by most significant
* bytes that contain the sign bits.
*
* @param array the array to sort.
* @param buffer the buffer array.
* @param counterMap the counter map. We pass this array in order not to
* create it in this method.
* @param fromIndex the starting, inclusive index of the sorting range.
* @param toIndex the ending, exclusive index of the sorting range.
*/
private static void countingSortImplSigned(int[] array,
int[] buffer,
int[] counterMap,
int fromIndex,
int toIndex) {
Arrays.fill(counterMap, 0);
// Count the elements:
for (int i = fromIndex; i != toIndex; i++) {
counterMap[extractCounterIndexSigned(array[i])]++;
}
// Make the counter map accummulative:
for (int i = 1; i != RADIX; i++) {
counterMap[i] += counterMap[i - 1];
}
// Build the output array:
for (int i = toIndex - 1; i >= fromIndex; i--) {
int index = extractCounterIndexSigned(array[i]);
buffer[--counterMap[index]] = array[i];
}
// Just copy the buffer to the array:
System.arraycopy(buffer,
0,
array,
fromIndex,
buffer.length);
}
/**
* Sorts the {@code array[fromIndex ... toIndex - 1]} by most significant
* bytes that contain the sign bits.
*
* @param array the array to sort.
* @param buffer the buffer array.
* @param counterMap the counter map. We pass this array in order not to
* create it in this method.
* @param fromIndex the starting, inclusive index of the sorting range.
* @param toIndex the ending, exclusive index of the sorting range.
*/
private static void countingSortImplSigned(long[] array,
long[] buffer,
int[] counterMap,
int fromIndex,
int toIndex) {
Arrays.fill(counterMap, 0);
// Count the elements:
for (int i = fromIndex; i != toIndex; i++) {
counterMap[extractCounterIndexSigned(array[i])]++;
}
// Make the counter map accummulative:
for (int i = 1; i != RADIX; i++) {
counterMap[i] += counterMap[i - 1];
}
// Build the output array:
for (int i = toIndex - 1; i >= fromIndex; i--) {
int index = extractCounterIndexSigned(array[i]);
buffer[--counterMap[index]] = array[i];
}
// Just copy the buffer to the array:
System.arraycopy(buffer,
0,
array,
fromIndex,
buffer.length);
}
/**
* Extracts the counter array index from the integer datum.
*
* @param datum the integer key.
* @param byteIndex the index of the byte of the key to consider.
* @return the index into counter array.
*/
private static int extractCounterIndex(int datum, int byteIndex) {
// Shift so that the target byte is the leftmost byte and set to zero
// all the remaining bits:
return (datum >>> (byteIndex * 8)) & 0xff;
}
/**
* Extracts the counter array index from the integer datum. Considers only
* the most significant byte that contains the sign bit. The sign bit is
* flipped in order to put the datum in correct location in the counter
* array.
*
* @param datum the integer key.
* @return the index into counter array.
*/
private static int extractCounterIndexSigned(int datum) {
// We use xor ^ operator in order to flip the bit index 7 (8th bit from
// the least significant end):
return (datum >>> 24) ^ 0b1000_0000;
}
/**
* Extracts the counter array index from the {@code long} integer datum.
*
* @param datum the {@code long} integer key.
* @param byteIndex the index of the byte of the key to consider.
* @return the index into counter array.
*/
private static int extractCounterIndex(long datum, int byteIndex) {
return (int)((datum >>> (byteIndex * 8)) & 0xffL);
}
/**
* Extracts the counter array index from the {@code long} integer datum.
* Considers only the most significant byte that contains the sign bit. The
* sign bit is flipped in order to put the datum in correct location in the
* counter array.
*
* @param datum the {@code long} integer key.
* @return the index into counter array.
*/
private static int extractCounterIndexSigned(long datum) {
return (int)((datum >>> 56) ^ 0b1000_0000);
}
/**
* Checks that the specified sorting range is reasonable.
*
* @param arrayLength the total length of the target array.
* @param fromIndex the starting, inclusive index of the sorting range.
* @param toIndex the ending, exclusive index of the sorting range.
*/
private static void checkRangeIndices(int arrayLength,
int fromIndex,
int toIndex) {
if (fromIndex < 0) {
throw new IllegalArgumentException(
String.format(
"fromIndex(%d) is negative. Must be at least 0.",
fromIndex));
}
if (toIndex > arrayLength) {
throw new IllegalArgumentException(
String.format(
"toIndex(%d) is too large. Must be at most %d.",
toIndex,
arrayLength));
}
if (fromIndex > toIndex) {
throw new IllegalArgumentException(
String.format(
"toIndex(%d) > fromIndex(%d).",
toIndex,
fromIndex));
}
}
}
com.github.coderodde.util.demo.LsdRadixsortDemo.java:
package com.github.coderodde.util.demo;
import com.github.coderodde.util.LsdRadixsort;
import java.util.Arrays;
import java.util.Random;
public class LsdRadixsortDemo {
private static final int LENGTH = 100_000_000;
private static final int PREFIX_SUFFIX_EXCLUSION_RANGE_LENGTH = 50;
public static void main(String[] args) {
long seed = System.currentTimeMillis();
Random random = new Random(seed);
int fromIndex =
random.nextInt(PREFIX_SUFFIX_EXCLUSION_RANGE_LENGTH + 1);
int toIndex = LENGTH - random.nextInt(
PREFIX_SUFFIX_EXCLUSION_RANGE_LENGTH + 1);
System.out.printf("Seed = %d.\n", seed);
////// int array:
System.out.println("--- int arrays ---");
long startTime = System.currentTimeMillis();
int[] intArray1 = createRandomIntegerArray(LENGTH, random);
int[] intArray2 = intArray1.clone();
long endTime = System.currentTimeMillis();
System.out.printf("Built demo int arrays in %d milliseconds.\n",
endTime - startTime);
startTime = System.currentTimeMillis();
LsdRadixsort.sort(intArray1, fromIndex, toIndex);
endTime = System.currentTimeMillis();
long durationRadixsort = endTime - startTime;
System.out.printf("LSDRadixsort took %d milliseconds.\n",
durationRadixsort);
startTime = System.currentTimeMillis();
Arrays.sort(intArray2, fromIndex, toIndex);
endTime = System.currentTimeMillis();
long durationArraysSort = endTime - startTime;
System.out.printf("Arrays.sort took %d milliseconds.\n",
durationArraysSort);
System.out.printf("Arrays agree: %b.\n",
Arrays.equals(intArray1,
intArray2));
float ratio = (float) durationRadixsort / (float) durationArraysSort;
System.out.println(
String.format(
"Time ratio: %.3f.\n", ratio)
.replace(',', '.'));
intArray1 = null;
intArray2 = null;
System.gc();
////// long array:
System.out.println("--- long arrays ---");
startTime = System.currentTimeMillis();
long[] longArray1 = createRandomLongIntegerArray(LENGTH, random);
long[] longArray2 = longArray1.clone();
endTime = System.currentTimeMillis();
System.out.printf("Built demo long arrays in %d milliseconds.\n",
endTime - startTime);
startTime = System.currentTimeMillis();
LsdRadixsort.sort(longArray1, fromIndex, toIndex);
endTime = System.currentTimeMillis();
durationRadixsort = endTime - startTime;
System.out.printf("LSDRadixsort took %d milliseconds.\n",
durationRadixsort);
startTime = System.currentTimeMillis();
Arrays.sort(longArray2, fromIndex, toIndex);
endTime = System.currentTimeMillis();
durationArraysSort = endTime - startTime;
System.out.printf("Arrays.sort took %d milliseconds.\n",
durationArraysSort);
System.out.printf("Arrays agree: %b.\n",
Arrays.equals(longArray1,
longArray2));
ratio = (float) durationRadixsort / (float) durationArraysSort;
System.out.println(
String.format(
"Time ratio: %.3f.\n", ratio)
.replace(',', '.'));
longArray1 = null;
longArray2 = null;
System.gc();
}
private static short[] createRandomShortArray(int length, Random random) {
short[] array = new short[length];
for (int i = 0; i < length; i++) {
array[i] = (short) random.nextInt();
}
return array;
}
private static int[] createRandomIntegerArray(int length, Random random) {
int[] array = new int[length];
for (int i = 0; i < length; i++) {
array[i] = random.nextInt();
}
return array;
}
private static long[] createRandomLongIntegerArray(int length,
Random random) {
long[] array = new long[length];
for (int i = 0; i < length; i++) {
array[i] = random.nextInt();
}
return array;
}
}
Typical output
Seed = 1710512066995.
--- int arrays ---
Built demo int arrays in 2916 milliseconds.
LSDRadixsort took 3074 milliseconds.
Arrays.sort took 16393 milliseconds.
Arrays agree: true.
Time ratio: 0.188.
--- long arrays ---
Built demo long arrays in 1874 milliseconds.
LSDRadixsort took 5880 milliseconds.
Arrays.sort took 16493 milliseconds.
Arrays agree: true.
Time ratio: 0.357.
Critique request
As always, I am eager to receive any commentary of my work.
random.nextInt()increateRandomLongIntegerArray()creates an unexpected distribution. \$\endgroup\$random.nextInt(1000), the LSD radix sort forints is 42% faster thanArrays.sort. \$\endgroup\$