I have rolled my own parallel merge sort. My performance figures are as follows:Seed: 1457521330571java.util.Arrays.sort() in 6840 ms. Sorted: truejava.util.Arrays.parallelSort() 3777 ms. Sorted: truenet.coderodde.util.sorting.ParallelMergesort.sort() 4498 ms. Sorted: trueArrays identical: trueClose, 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.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;    }}
Parallel merge sort in Java
java;algorithm;multithreading;sorting;mergesort