• 20.5k
• 6
• 69
• 155

• 31.8k
• 15
• 77
• 202

I have rolled my own parallel merge sort and it looks like this:

ParallelMergesort.java:

package net.coderodde.util.sorting;
import java.util.Arrays;
/**
 * This class implements a parallel merge sort.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 9, 2016)
 */
public class ParallelMergesort {
 private static final int MINIMUM_THREAD_WORKLOAD = 100_000;
 public static <T extends Comparable<? super T>> void sort(T[] array) {
 sort(array, 0, array.length);
 }
 public static <T extends Comparable<? super T>> void sort(T[] array,
 int fromIndex,
 int toIndex) {
 int rangeLength = toIndex - fromIndex;
 int threads = Math.min(rangeLength / MINIMUM_THREAD_WORKLOAD,
 Runtime.getRuntime().availableProcessors());
 threads = fixThreadCount(threads);
 if (threads < 2) {
 BottomUpMergesort.sort(array, fromIndex, toIndex);
 return;
 }
 int leftPartLength = rangeLength >>> 1;
 int rightPartLength = rangeLength - leftPartLength;
 T[] aux = Arrays.copyOfRange(array, fromIndex, toIndex);
 SorterThread<T> thread1 = new SorterThread<>(threads >>> 1,
 array,
 aux,
 fromIndex,
 0,
 leftPartLength);
 thread1.start();
 SorterThread<T> thread2 = new SorterThread<>(threads - threads >>> 1,
 array,
 aux,
 fromIndex + leftPartLength,
 leftPartLength,
 rightPartLength);
 thread2.run();
 try {
 thread1.join();
 } catch (InterruptedException ex) {
 throw new IllegalStateException(
 "A SorterThread threw an IllegalStateException.");
 }
 merge(aux, array, 0, fromIndex, leftPartLength, rightPartLength);
 }
 private static <T extends Comparable<? super T>> 
 void merge(T[] source,
 T[] target,
 int sourceOffset,
 int targetOffset,
 int leftRunLength,
 int rightRunLength) {
 int left = sourceOffset;
 int leftUpperBound = sourceOffset + leftRunLength;
 int right = leftUpperBound;
 int rightUpperBound = leftUpperBound + rightRunLength;
 int targetIndex = targetOffset;
 while (left < leftUpperBound && right < rightUpperBound) {
 target[targetIndex++] =
 source[right].compareTo(source[left]) < 0 ?
 source[right++] :
 source[left++];
 }
 System.arraycopy(source, 
 left, 
 target, 
 targetIndex, 
 leftUpperBound - left);
 System.arraycopy(source, 
 right, 
 target, 
 targetIndex, 
 rightUpperBound - right);
 }
 private static int fixThreadCount(int threads) {
 int ret = 1;
 while (ret < threads) {
 ret <<= 1;
 }
 return ret;
 }
 private static final class SorterThread<T extends Comparable<? super T>> 
 extends Thread {
 private final int threads;
 private final T[] source;
 private final T[] target;
 private final int sourceOffset;
 private final int targetOffset;
 private final int rangeLength;
 SorterThread(int threads,
 T[] source,
 T[] target,
 int sourceOffset, 
 int targetOffset,
 int rangeLength) {
 this.threads = threads;
 this.source = source;
 this.target = target;
 this.sourceOffset = sourceOffset;
 this.targetOffset = targetOffset;
 this.rangeLength = rangeLength;
 }
 @Override
 public void run() {
 if (threads < 2) {
 BottomUpMergesort.sort(target,
 targetOffset,
 targetOffset + rangeLength);
 return;
 }
 int leftPartLength = rangeLength / 2;
 SorterThread<T> thread1 = new SorterThread<>(threads / 2,
 target,
 source,
 targetOffset,
 sourceOffset,
 leftPartLength);
 thread1.start();
 SorterThread<T> thread2 = new SorterThread<>(
 threads - threads / 2,
 target, 
 source,
 targetOffset + leftPartLength,
 sourceOffset + leftPartLength,
 rangeLength - leftPartLength);
 thread2.run();
 try {
 thread1.join();
 } catch (InterruptedException ex) {
 throw new IllegalStateException(
 "A SorterThread threw InterruptedException.");
 }
 merge(source, 
 target, 
 sourceOffset, 
 targetOffset, 
 leftPartLength,
 rangeLength - leftPartLength);
 }
 }
}

BottomUpMergesort.java:

package net.coderodde.util.sorting;
import java.util.Arrays;
/**
 * This class provides static methods for sorting object arrays using 
 * bottom-up (non-recursive) merge sort.
 * <p>
 * Initially, the input range is divided into chunks of 
 * {@code insertionsortThreshold} elements and are sorted using insertion sort.
 * (The last chunk is allowed to be shorter.) After that they are merged 
 * pairwise until the input range is sorted.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 * @param <T> the actual array component type.
 */
public class BottomUpMergesort<T extends Comparable<? super T>> {
 private static final int INSERTIONSORT_THRESHOLD = 16;
 /**
 * The actual array containing the range to be sorted.
 */
 private final T[] array;
 /**
 * The helper array for merging.
 */
 private final T[] buffer;
 /**
 * The starting (inclusive) index of the range to be sorted.
 */
 private final int fromIdx;
 /**
 * The length of the range being sorted.
 */
 private final int rangeLength;
 /**
 * The array holding current source array.
 */
 private T[] source;
 /**
 * The array holding current target array.
 */
 private T[] target;
 /**
 * The amount of array components at the beginning to skip from 
 * consideration in the source array.
 */
 private int sourceOffset;
 /**
 * The amount of array components at the beginning to skip from 
 * consideration in the target array. 
 */
 private int targetOffset;
 /**
 * Constructs a new sort object holding the state of sorting procedure.
 * 
 * @param array the array containing the requested sort range.
 * @param fromIndex the starting (inclusive) index of the range to sort.
 * @param toIndex the ending (exclusive) index of the range to sort.
 * @param cmp the array component comparator.
 */
 private BottomUpMergesort(T[] array, 
 int fromIndex, 
 int toIndex) {
 if (array == null) {
 throw new NullPointerException("The input array is null.");
 }
 rangeCheck(array.length, fromIndex, toIndex);
 this.fromIdx = fromIndex;
 this.array = array;
 this.rangeLength = toIndex - fromIndex;
 this.buffer = Arrays.copyOfRange(array, fromIndex, toIndex);
 }
 /**
 * Performs the actual sorting.
 */
 private void sort() {
 if (rangeLength < 2) {
 return;
 }
 int runs = computeRunAmount();
 int mergePasses = computeAmountOfMergingPasses(runs);
 if (mergePasses % 2 == 0) {
 // We will need an even amount of merging passes over the input 
 // range in order to sort it. Let the input array be source so that 
 // the sorted range ends up in it.
 this.source = array;
 this.target = buffer;
 this.sourceOffset = fromIdx;
 this.targetOffset = 0;
 } else {
 // We need an odd number of merging passes over the input range in
 // order to sort it. Let the auxiliary buffer be the source so that
 // the sorted range ends up in the input array.
 this.source = buffer;
 this.target = array;
 this.sourceOffset = 0;
 this.targetOffset = fromIdx;
 }
 // Make the requested range be sorted into sorted chunks, each of length
 // 'insertionsortThreshold'. The last chunk may be shorter than that
 // threshold value.
 presortRuns(runs);
 // Initial runs are ready to be merged. 'runLength <<= 1' multiplies
 // 'runLength' by 2.
 for (int runLength = INSERTIONSORT_THRESHOLD; 
 runLength < rangeLength;
 runLength <<= 1) {
 mergePass(runs, runLength);
 // 'runs >>> 1' divides 'runs' by 2 ignoring the decimals.
 // '(runs & 1) != 0 ? 1 : 0' is zero if 'runs' is even, and one
 // otherwise.
 runs = (runs >>> 1) + ((runs & 1) != 0 ? 1 : 0);
 // Now make the target array a source array, and vice versa.
 swapArrayRoles();
 }
 }
 /**
 * Makes the source array a target array, and the target array a source 
 * array. Adjusts also the offsets of the two arrays.
 */
 private void swapArrayRoles() {
 // Swap the array roles.
 T[] tmparr = source;
 source = target;
 target = tmparr;
 // Swap the array offsets.
 int tmpOffset = sourceOffset;
 sourceOffset = targetOffset;
 targetOffset = tmpOffset;
 }
 /**
 * Computes the amount of runs in the requested range that are to be sorted
 * using insertion sort.
 * 
 * @return the amount of runs.
 */
 private int computeRunAmount() {
 return rangeLength / INSERTIONSORT_THRESHOLD +
 (rangeLength % INSERTIONSORT_THRESHOLD != 0 ? 1 : 0);
 }
 /**
 * Computes the amount of merging passes needed to be performed in order to
 * sort the requested range.
 * 
 * @param runs the amount of runs in the requested input range after
 * insertion sort was applied to small chunks.
 * @return the amount of merging passes needed to sort the input range.
 */
 private int computeAmountOfMergingPasses(int runs) {
 return 32 - Integer.numberOfLeadingZeros(runs - 1);
 }
 /**
 * Presorts the input range so that it contains sorted chunks of length
 * {@code insertionsortThreshold}. The last run may be shorter.
 * 
 * @param runs the amount of runs the requested range contains of.
 */
 private void presortRuns(int runs) {
 int localFromIndex = sourceOffset;
 // Presort all but the last chunk in the source array.
 for (int i = 0; i < runs - 1; ++i) {
 insertionSort(source, 
 localFromIndex, 
 localFromIndex += INSERTIONSORT_THRESHOLD);
 }
 // Presort the last chunk that may be shorter than 
 // 'insertionsortThreshold'.
 insertionSort(source,
 localFromIndex,
 Math.min(sourceOffset + rangeLength, 
 localFromIndex + INSERTIONSORT_THRESHOLD));
 }
 /**
 * Merges the first run with the second one, the third one with the fourth
 * one, and so on until all possible merges are performed. If there is an
 * odd number of runs, the last one is copied into the target array as it 
 * may appear in the target array as two smaller unmerged runs.
 * 
 * @param runs the amount of runs in the source array.
 * @param runLength the current run length.
 * @return the amount of runs merged.
 */
 private void mergePass(int runs, int runLength) {
 int runIndex = 0;
 for (; runIndex < runs - 1; runIndex += 2) {
 // Set up the indices.
 int leftIndex = sourceOffset + runIndex * runLength;
 int leftBound = leftIndex + runLength;
 int rightBound = Math.min(leftBound + runLength, 
 rangeLength + sourceOffset);
 int targetIndex = targetOffset + runIndex * runLength;
 // Perform the actual merging.
 merge(leftIndex, leftBound, rightBound, targetIndex);
 }
 if (runIndex < runs) {
 // There was an odd number of runs in the source array, and
 // thus, the last run was an "orphan" run. We need to copy it 
 // to the current target array as it may appear there as two
 // smaller unmerged runs.
 System.arraycopy(source,
 sourceOffset + runIndex * runLength,
 target,
 targetOffset + runIndex * runLength,
 rangeLength - runIndex * runLength);
 }
 }
 /**
 * Sorts the entire array.
 * 
 * @param <T> the array component type.
 * @param array the array to sort.
 */
 public static <T extends Comparable<? super T>> void sort(T[] array) {
 sort(array, 0, array.length);
 }
 /**
 * Sorts the range {@code array[fromIndex], array[fromIndex + 1], ..., 
 * array[toIndex - 2], array[toIndex - 1]}.
 * 
 * @param <T> the array component type.
 * @param array the array containing the requested range.
 * @param fromIndex the starting (inclusive) index of the range to sort.
 * @param toIndex the ending (exclusive) index of the range to sort.
 */
 public static <T extends Comparable<? super T>> void sort(T[] array, 
 int fromIndex, 
 int toIndex) {
 new BottomUpMergesort(array, fromIndex, toIndex).sort();
 }
 /**
 * Sorts the range {@code array[fromIndex,], array[fromIndex + 1], ...,
 * array[toIndex - 2], array[toIndex - 1]} using insertion sort. This 
 * implementation is <b>stable</b>.
 * 
 * @param <T> the array component type.
 * @param array the array holding the requested range.
 * @param fromIndex the starting (inclusive) index.
 * @param toIndex the ending (exclusive) index.
 */
 public static <T extends Comparable<? super T>> 
 void insertionSort(T[] array,
 int fromIndex,
 int toIndex) {
 for (int i = fromIndex + 1; i < toIndex; ++i) {
 T element = array[i];
 int j = i;
 for (; j > fromIndex && array[j - 1].compareTo(element) > 0; --j) {
 array[j] = array[j - 1];
 }
 array[j] = element;
 }
 }
 /**
 * Merges the sorted ranges {@code source[leftIndex, leftBound)} and
 * {@code source[rightIndex, rightBound)} putting the result to 
 * {@code target} starting from component with index {@code targetIndex}.
 * 
 * @param <T> the array component type.
 * @param source the source array.
 * @param target the target array.
 * @param leftIndex the (inclusive) starting index of the left run.
 * @param leftBound the (exclusive) ending index of the left run.
 * @param rightIndex the (inclusive) starting index of the right run.
 * @param rightBound the (exclusive) ending index of the right run.
 * @param targetIndex the starting index of the result run in the target
 * array.
 * @param cmp the element comparator.
 */
 private void merge(int leftIndex,
 int leftBound,
 int rightBound,
 int targetIndex) {
 int rightIndex = leftBound;
 while (leftIndex < leftBound && rightIndex < rightBound) {
 target[targetIndex++] = 
 source[rightIndex].compareTo(source[leftIndex]) < 0 ?
 source[rightIndex++] :
 source[leftIndex++];
 }
 System.arraycopy(source, 
 leftIndex, 
 target, 
 targetIndex, 
 leftBound - leftIndex);
 System.arraycopy(source, 
 rightIndex, 
 target, 
 targetIndex, 
 rightBound - rightIndex);
 }
 /**
 * Checks that {@code fromIndex} and {@code toIndex} are sensible and throws
 * an exception if they are not.
 * 
 * @param arrayLength the length of the array.
 * @param fromIndex the starting (inclusive) index of the range to sort.
 * @param toIndex the ending (exclusive) index of the range to sort.
 * @throws IllegalArgumentException if {@code fromIndex} is larger than
 * {@code toIndex}.
 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex} is negative
 * of {@code toIndex} is too large.
 */
 private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
 if (fromIndex > toIndex) {
 throw new IllegalArgumentException(
 "'fromIndex' is larger than 'toIndex': " +
 fromIndex + " > " + toIndex);
 }
 if (fromIndex < 0) {
 throw new ArrayIndexOutOfBoundsException(
 "'fromIndex' is negative: " + fromIndex);
 }
 if (toIndex > arrayLength) {
 throw new ArrayIndexOutOfBoundsException(
 "'toIndex' is too large: " + toIndex + ", array length: " +
 arrayLength);
 }
 }
}

Demo.java:

import java.util.Arrays;
import java.util.Random;
import net.coderodde.util.sorting.ParallelMergesort;
public class Demo {
 private static final int SIZE = 10_000_000;
 private static final int FROM_INDEX = 3;
 private static final int TO_INDEX = SIZE - 2;
 public static void main(String[] args) {
 long seed = 1457521330571L; System.currentTimeMillis();
 Random random = new Random(seed);
 Integer[] array1 = createRandomIntegerArray(SIZE, random);
 Integer[] array2 = array1.clone();
 Integer[] array3 = array1.clone();
 System.out.println("JVM: I am warming up.");
 //// Warming up.
 for (int i = 0; i < 5; ++i) {
 Integer[] arr1 = createRandomIntegerArray(500_000, random);
 Integer[] arr2 = arr1.clone();
 Integer[] arr3 = arr1.clone();
 Arrays.sort(arr1);
 Arrays.parallelSort(arr2);
 ParallelMergesort.sort(arr3);
 }
 System.out.println("JVM: I am warm now.");
 System.out.println("Seed: " + seed);
 //// java.util.Arrays.sort
 long ta = System.currentTimeMillis();
 Arrays.sort(array1, FROM_INDEX, TO_INDEX);
 long tb = System.currentTimeMillis();
 System.out.println(
 "java.util.Arrays.sort() in " + (tb - ta) + " ms. Sorted: " +
 isSorted(array1, FROM_INDEX, TO_INDEX));
 //// java.util.Arrays.parallelSort
 ta = System.currentTimeMillis();
 Arrays.parallelSort(array2, FROM_INDEX, TO_INDEX);
 tb = System.currentTimeMillis();
 System.out.println(
 "java.util.Arrays.parallelSort() " +
 (tb - ta) + " ms. Sorted: " + 
 isSorted(array2, FROM_INDEX, TO_INDEX));
 //// net.coderodde.util.sorting.BottomUpMergesort.sort
 ta = System.currentTimeMillis();
 ParallelMergesort.sort(array3, FROM_INDEX, TO_INDEX);
 tb = System.currentTimeMillis();
 System.out.println(
 "net.coderodde.util.sorting.ParallelMergesort.sort() " +
 (tb - ta) + " ms. Sorted: " + 
 isSorted(array3, FROM_INDEX, TO_INDEX));
 System.out.println(
 "Arrays identical: " + 
 (Arrays.equals(array1, array2)
 && Arrays.equals(array1, array3)));
 }
 static <T extends Comparable<? super T>> boolean isSorted(T[] array,
 int fromIndex,
 int toIndex) {
 for (int i = fromIndex; i < toIndex - 1; ++i) {
 if (array[i].compareTo(array[i + 1]) > 0) {
 return false;
 }
 }
 return true;
 }
 static <T extends Comparable<? super T>> boolean isSorted(T[] array) {
 return isSorted(array, 0, array.length);
 }
 static <T> boolean arraysIdentical(T[] arr1, T[] arr2) {
 if (arr1.length != arr2.length) {
 return false;
 }
 for (int i = 0; i < arr1.length; ++i) {
 if (arr1[i] != arr2[i]) {
 return false;
 }
 }
 return true;
 }
 static Integer[] createRandomIntegerArray(int size, Random random) {
 Integer[] ret = new Integer[size];
 for (int i = 0; i < size; ++i) {
 ret[i] = random.nextInt(size);
 }
 return ret;
 }
}

My performance figures are as follows:

Seed: 1457521330571
java.util.Arrays.sort() in 6840 ms. Sorted: true
java.util.Arrays.parallelSort() 3777 ms. Sorted: true
net.coderodde.util.sorting.ParallelMergesort.sort() 4498 ms. Sorted: true
Arrays identical: true

Close, but no cigar. I would like to hear whatever you come up with, however, it would be nice to find out how to speed up my implementation.