I have this MSD (most-significant digit) radix sort sorting Entry objects holding a sorting key of type long and a satellite datum. It handles the issue of sign bits so that it produces a permutation that honours the sign bit: the Entry with the sign bit on will precede all the Entry objects with sign bit off.
It is highly efficient on large arrays (almost 3 times faster than java.util.Arrays.sort to sort 1e7 Entry objects).
So what do you think?
Arrays.java:
package net.coderodde.util;
public class Arrays {
private static final int BUCKETS = 256;
private static final int BITS_PER_BYTE = 8;
private static final int RIGHT_SHIFT_AMOUNT = 56;
private static final int MOST_SIGNIFICANT_BYTE_INDEX = 7;
private static final int MERGESORT_THRESHOLD = 4096;
private static final int LEAST_SIGNED_BUCKET_INDEX = 128;
public static final <E> void sort(final Entry<E>[] array,
final int fromIndex,
final int toIndex) {
if (toIndex - fromIndex < 2) {
// Trivially sorted or indices ass-backwards.
return;
}
final Entry<E>[] buffer = array.clone();
sortTopImpl(array, buffer, fromIndex, toIndex);
}
public static final <E> void sort(final Entry<E>[] array) {
sort(array, 0, array.length);
}
public static final <E extends Comparable<? super E>>
boolean isSorted(final E[] array,
final int fromIndex,
final int toIndex) {
for (int i = fromIndex; i < toIndex - 1; ++i) {
if (array[i].compareTo(array[i + 1]) > 0) {
return false;
}
}
return true;
}
public static final <E extends Comparable<? super E>>
boolean isSorted(final E[] array) {
return isSorted(array, 0, array.length);
}
public static final <E> boolean areEqual(final Entry<E>[]... arrays) {
for (int i = 0; i < arrays.length - 1; ++i) {
if (arrays[i].length != arrays[i + 1].length) {
return false;
}
}
for (int i = 0; i < arrays[0].length; ++i) {
for (int j = 0; j < arrays.length - 1; ++j) {
if (arrays[j][i] != arrays[j + 1][i]) {
return false;
}
}
}
return true;
}
/**
* This static method sorts sequentially an entry array by most-significant
* bytes.
*
* @param <E> the type of satellite data of each entry.
* @param array the actual array to sort.
* @param buffer the auxiliary buffer.
* @param fromIndex the least index of the range to sort.
* @param toIndex the index one past the last index of the range to sort.
*/
private static <E> void sortTopImpl(final Entry<E>[] array,
final Entry<E>[] buffer,
final int fromIndex,
final int toIndex) {
// The amount of elements in the requested range.
final int RANGE_LENGTH = toIndex - fromIndex;
if (RANGE_LENGTH <= MERGESORT_THRESHOLD) {
// Once here, the range is too small, use merge sort.
// The amount of merge passes needed to sort the input range.
final int PASSES = getPassAmount(RANGE_LENGTH);
// Here, both 'array' and 'buffer' are identical in content.
if ((PASSES & 1) == 0) {
// Once here, there will be an even amount of merge passes, so
// it makes sense to pass 'array' as the source array so that
// the actual sorted data ends up in it, so there is no need
// to copy the sorted range from 'buffer' to 'array'.
mergesort(array, buffer, fromIndex, toIndex);
} else {
// A symmetric case: sort using 'buffer' as the source array
// so that the sorted data ends up in 'array' and we don't have
// to do additional copying.
mergesort(buffer, array, fromIndex, toIndex);
}
return;
}
final int[] bucketSizeMap = new int[BUCKETS];
final int[] startIndexMap = new int[BUCKETS];
final int[] processedMap = new int[BUCKETS];
// Determine the size of each bucket.
for (int i = fromIndex; i < toIndex; ++i) {
bucketSizeMap[(int)(array[i].key >>> RIGHT_SHIFT_AMOUNT)]++;
}
// BEGIN: Special sign bit magic.
startIndexMap[LEAST_SIGNED_BUCKET_INDEX] = fromIndex;
for (int i = LEAST_SIGNED_BUCKET_INDEX + 1; i != BUCKETS; ++i) {
startIndexMap[i] = startIndexMap[i - 1] +
bucketSizeMap[i - 1];
}
startIndexMap[0] = startIndexMap[BUCKETS - 1] +
bucketSizeMap[BUCKETS - 1];
for (int i = 1; i != LEAST_SIGNED_BUCKET_INDEX; ++i) {
startIndexMap[i] = startIndexMap[i - 1] +
bucketSizeMap[i - 1];
}
// END: Special sign bit magic.
// Insert elements into their respective buckets in the buffer array.
for (int i = fromIndex; i < toIndex; ++i) {
final Entry<E> e = array[i];
final int index = (int)(e.key >>> RIGHT_SHIFT_AMOUNT);
buffer[startIndexMap[index] + processedMap[index]++] = e;
}
// Recur to sort all non-empty buckets.
for (int i = 0; i != BUCKETS; ++i) {
if (bucketSizeMap[i] != 0) {
sortImpl(buffer,
array,
MOST_SIGNIFICANT_BYTE_INDEX - 1,
startIndexMap[i],
startIndexMap[i] + bucketSizeMap[i]);
}
}
}
/**
* This static method sorts the entry array by bytes that are not
* most-significant.
*
* @param <E> the type of satellite data in the entry array.
* @param source the source array.
* @param target the target array.
* @param byteIndex the index of the byte to use as the sorting key. 0
* represents the least-significant byte.
* @param fromIndex the least index of the range to sort.
* @param toIndex the index one past the greatest index of the range to
* sort.
*/
private static <E> void sortImpl(final Entry<E>[] source,
final Entry<E>[] target,
final int byteIndex,
final int fromIndex,
final int toIndex) {
// Try merge sort.
if (toIndex - fromIndex <= MERGESORT_THRESHOLD) {
// If 'even' is true, the sorted ranged ended up in 'source'.
final boolean even = mergesort(source, target, fromIndex, toIndex);
if (even) {
// source contains the sorted bucket.
if ((byteIndex & 1) == 0) {
// byteIndex = 6, 4, 2, 0.
// source is buffer, copy to target.
System.arraycopy(source,
fromIndex,
target,
fromIndex,
toIndex - fromIndex);
}
} else {
// target contains the sorted bucket.
if ((byteIndex & 1) == 1) {
// byteIndex = 5, 3, 1.
// target is buffer, copy to source.
System.arraycopy(target,
fromIndex,
source,
fromIndex,
toIndex - fromIndex);
}
}
return;
}
final int[] bucketSizeMap = new int[BUCKETS];
final int[] startIndexMap = new int[BUCKETS];
final int[] processedMap = new int[BUCKETS];
// We need this as to get rid of the bits on the left from the byte we
// are interesed in.
final int LEFT_SHIFT_AMOUNT =
BITS_PER_BYTE * (MOST_SIGNIFICANT_BYTE_INDEX - byteIndex);
// Compute the size of each bucket.
for (int i = fromIndex; i < toIndex; ++i) {
bucketSizeMap[(int)((source[i].key << LEFT_SHIFT_AMOUNT)
>>> RIGHT_SHIFT_AMOUNT)]++;
}
// Initialize the start index map.
startIndexMap[0] = fromIndex;
// Compute the start index map in its entirety.
for (int i = 1; i != BUCKETS; ++i) {
startIndexMap[i] = startIndexMap[i - 1] +
bucketSizeMap[i - 1];
}
// Insert the entries from 'source' into their respective 'target'.
for (int i = fromIndex; i < toIndex; ++i) {
final Entry<E> e = source[i];
final int index = (int)((e.key << LEFT_SHIFT_AMOUNT)
>>> RIGHT_SHIFT_AMOUNT);
target[startIndexMap[index] + processedMap[index]++] = e;
}
if (byteIndex == 0) {
// There is nowhere to recur, return.
return;
}
// Recur to sort each bucket.
for (int i = 0; i != BUCKETS; ++i) {
if (bucketSizeMap[i] != 0) {
sortImpl(target,
source,
byteIndex - 1,
startIndexMap[i],
startIndexMap[i] + bucketSizeMap[i]);
}
}
}
/**
* Sorts the range <code>[fromIndex, toIndex)</code> between the arrays
* <code>source</code> and <code>target</code>.
*
* @param <E> the type of entries' satellite data.
* @param source the source array; the data to sort is assumed to be in this
* array.
* @param target acts as an auxiliary array.
* @param fromIndex the least component index of the range to sort.
* @param toIndex <code>toIndex - 1</code> is the index of the rightmost
* component in the range to sort.
* @return <code>true</code> if there was an even amount of merge passes,
* which implies that the sorted range ended up in <code>source</code>.
* Otherwise <code>false</code> is returned, and the sorted range ended up
* in the array <code>target</code>.
*/
private static final <E> boolean mergesort(final Entry<E>[] source,
final Entry<E>[] target,
final int fromIndex,
final int toIndex) {
final int RANGE_LENGTH = toIndex - fromIndex;
Entry<E>[] s = source;
Entry<E>[] t = target;
int passes = 0;
for (int width = 1; width < RANGE_LENGTH; width <<= 1) {
++passes;
int c = 0;
for (; c < RANGE_LENGTH / width; c += 2) {
int left = fromIndex + c * width;
int right = left + width;
int i = left;
final int leftBound = right;
final int rightBound = Math.min(toIndex, right + width);
while (left < leftBound && right < rightBound) {
t[i++] = s[right].key < s[left].key ?
s[right++] :
s[left++];
}
while (left < leftBound) { t[i++] = s[left++]; }
while (right < rightBound) { t[i++] = s[right++]; }
}
if (c * width < RANGE_LENGTH) {
for (int i = fromIndex + c * width; i < toIndex; ++i) {
t[i] = s[i];
}
}
final Entry<E>[] tmp = s;
s = t;
t = tmp;
}
return (passes & 1) == 0;
}
private static int getPassAmount(int length) {
if (length < 1) {
// Should not get here.
length = 1;
}
return 32 - Integer.numberOfLeadingZeros(length - 1);
}
}
Entry.java:
package net.coderodde.util;
/**
* The wrapper class holding a satellite datum and the key.
*
* @param <E> the type of a satellite datum.
*/
public final class Entry<E> implements Comparable<Entry<E>> {
/**
* The sorting key.
*/
public long key;
/**
* The satellite data.
*/
public E satelliteData;
/**
* Constructs a new <code>Entry</code> with key <code>key</code> and
* the satellite datum <code>satelliteData</code>.
*
* @param key the key of this entry.
* @param satelliteData the satellite data associated with the key.
*/
public Entry(final long key, final E satelliteData) {
this.key = key;
this.satelliteData = satelliteData;
}
/**
* Compares this <code>Entry</code> with another.
*
* @param o the entry to compare against.
*
* @return a negative value if this entry's key is less than that of
* <code>o</code>, a positive value if this entry's key is greater than that
* of <code>o</code>, or 0 if the two keys are equal.
*/
@Override
public int compareTo(Entry<E> o) {
if (key < o.key) {
return -1;
} else if (key > o.key) {
return 1;
} else {
return 0;
}
}
}
Demo.java:
package net.coderodde.util;
import java.util.Random;
public class Demo {
private static final int N = 10000000;
public static void main(final String... args) {
final long seed = System.currentTimeMillis();
final Random rnd = new Random(seed);
final Entry<Integer>[] array1 = getRandomEntryArray(N, rnd);
final Entry<Integer>[] array2 = array1.clone();
System.out.println("Seed: " + seed);
long ta = System.currentTimeMillis();
net.coderodde.util.Arrays.sort(array1);
long tb = System.currentTimeMillis();
System.out.println("net.coderodde.util.Arrays.sort in " +
(tb - ta) + " ms.");
ta = System.currentTimeMillis();
java.util.Arrays.sort(array2);
tb = System.currentTimeMillis();
System.out.println("java.util.Arrays.sort in " +
(tb - ta) + " ms.");
System.out.println("Arrays are equal: " +
Arrays.areEqual(array1, array2));
System.out.println("Sorted: " + Arrays.isSorted(array1));
}
private static Entry<Integer>[] getRandomEntryArray(final int size,
final Random rnd) {
final Entry<Integer>[] array = new Entry[size];
for (int i = 0; i < size; ++i) {
array[i] = new Entry<>(rnd.nextLong(), null);
}
return array;
}
}
