# Efficient least-significant digit (LSD) radix sort for int and long keys in Java - iteration II

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;

}

/**
* 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 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();
endTime = System.currentTimeMillis();
long durationRadixsort = endTime - startTime;

System.out.printf("LSDRadixsort took %d milliseconds.\n",

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();
endTime = System.currentTimeMillis();
durationRadixsort = endTime - startTime;

System.out.printf("LSDRadixsort took %d milliseconds.\n",

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.

• I think using random.nextInt() in createRandomLongIntegerArray() creates an unexpected distribution. Commented Mar 15 at 14:46
• @greybeard True, but even with random.nextInt(1000), the LSD radix sort for ints is 42% faster than Arrays.sort. Commented Mar 15 at 15:26