Parallel MSD radix sort in Java

I have this parallel implementation of MSD radix sort, which processes the entries by one particular byte. At each byte index, it has three phases:

• Count the bucket sizes.

• Insert each entry to its bucket.

• Recur on each resulting bucket, if there are less-significant bytes to process.

The only synchronization primitive in this implementation is joining the threads upon the ends of each phase 1, 2, 3.

CoderoddeArrays.java:

```
package net.coderodde.util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Objects;

public class CoderoddeArrays {

private static final int BITS_PER_BUCKET = 8;
private static final int BUCKETS = 1 void parallelSort(final Entry[] array) {
parallelSort(array, 0, array.length);
}

public static void parallelSort(final Entry[] array,
final int fromIndex,
final int toIndex) {
final int RANGE_LENGTH = toIndex - fromIndex;

if (RANGE_LENGTH [] buffer = array.clone();
final int threads = Math.min(RANGE_LENGTH / THREAD_THRESHOLD,
Runtime.getRuntime()
.availableProcessors());
parallelSortImpl(array, buffer, threads, 0, fromIndex, toIndex);
}

public static final boolean areEqual(final Entry[]... arrays) {
for (int i = 0; i >
boolean isSorted(final E[] array,
final int fromIndex,
final int toIndex) {
for (int i = fromIndex; i 0) {
return false;
}
}

return true;
}

public static final >
boolean isSorted(final E[] array) {
return isSorted(array, 0, array.length);
}

private static final void sortImpl(final Entry[] source,
final Entry[] ta

Very nice.

private static final int THREAD_THRESHOLD = 65536;
private static final int MERGESORT_THRESHOLD = 4096;

These seem arbitrary. THREAD_THRESHOLD is perhaps "infinite" with a sanity check, that's fine. But MERGESORT_THRESHOLD seems like it wants an accompanying comment, a reference that describes how some benchmark fared worse with higher or lower thresholds. I'm especially concerned that the optimal threshold would be sensitive to cache size, and no guidance is offered on how to compare the system I'm running on today with the historic benchmark system.

A broader observation is that there's no guidance offered for how, on data of interest, this sort stacks up against the competition, such as in https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html .

Rather than using Runtime.getRuntime().availableProcessors(), consider assigning that (as default value) to some config parameter. This offers control to a caller that already has some busy BG threads.

The final loops in areEqual() are fairly pedestrian. Even though modern JITs can do wonders, it seems like Arrays or some other module should offer direct access to memcmp(), since we just need to know if every bit of src matches the bits of dst. I have a concern about whether the current approach of iterating first over array items, then over arrays, would be as cache friendly as the order memcmp() would use. Benching it both ways would be instructive.

ParallelSortImpl might break out helpers to explicitly name each of the three phases. In three places it attempts .join() and then:

} catch (final InterruptedException ie) {
        ie.printStackTrace();
        return;
    }

It seems likely this allows corrupted (unsorted) results to be passed back to callers. Consider, at a minimum, setting a dirty flag in the handler. Then top-level return to caller can consult flag, do final linear pass to check that all is sorted, and raise exception if not. Or, simply re-throw ie as a RuntimeException if this is a "can't happen" clause that you wrote just to keep the compiler happy about checked exceptions.

StackExchange Code Review Q#74297, answer score: 2