Parallel integer Quicksort in Java

Now I have that parallel Quicksort for (primitive) integer arrays.

ParallelIntQuicksort.java:

```
package net.coderodde.util;

import static net.coderodde.util.Util.median;
import static net.coderodde.util.Util.swap;

/**
* This class implements a parallel Quicksort.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Mar 5, 2016)
*/
public class ParallelIntQuicksort {

private static final int MINIMUM_THREAD_WORKLOAD = 131_072;

public static void sort(int[] array) {
sort(array, 0, array.length);
}

public static void sort(int[] array, int fromIndex, int toIndex) {
int rangeLength = toIndex - fromIndex;
int cores = Math.min(rangeLength / MINIMUM_THREAD_WORKLOAD,
Runtime.getRuntime().availableProcessors());
sortImpl(array,
fromIndex,
toIndex,
cores);
}

private ParallelIntQuicksort() {

}

private static void sortImpl(int[] array,
int fromIndex,
int toIndex,
int cores) {
if (cores >> 1)];
int c = array[toIndex - distance];

int pivot = median(a, b, c);
int leftPartitionLength = 0;
int rightPartitionLength = 0;
int index = fromIndex;

while (index pivot) {
++rightPartitionLength;
swap(array, toIndex - rightPartitionLength, index);
} else if (current < pivot) {
swap(array, fromIndex + leftPartitionLength, index);
++index;
++leftPartitionLength;
} else {
++index;
}
}

ParallelQuicksortThread leftThread =
new ParallelQuicksortThread(array,
fromIndex,
fromIndex + leftPartitionLength,

One thing that comes to mind is that you are forking more new threads than you need to.

ParallelQuicksortThread leftThread = 
            new ParallelQuicksortThread(array,
                                        fromIndex,
                                        fromIndex + leftPartitionLength,
                                        cores / 2);
    ParallelQuicksortThread rightThread =
            new ParallelQuicksortThread(array,
                                        toIndex - rightPartitionLength,
                                        toIndex,
                                        cores - cores / 2);

Since the current thread is not going to be doing anything until it joins with both of leftThread and rightThread, you could actually do the work of one of those two threads on the current thread. That saves the overhead of creating a thread.

The other comment is that the "best" speedup (IntQuicksort versus ParallelIntQuicksort) that you are seeing is in the ballpark of what I would expect for a 2 core machine. A significant amount of work (the initial partitioning) has to be done on the first thread before it forks the child threads. Also note that if the initial partitioning gives partitions whose sizes are very different, then workload won't be balanced. One thread will finish a lot sooner than the other, and the overall speedup won't be as great.

Finally, I am a bit dubious of your benchmarking methodology. You don't seem to allow for JVM warmup effects.

StackExchange Code Review Q#121996, answer score: 4