5
\$\begingroup\$

I have rolled my own parallel merge sort. 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.

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;
    }
}
\$\endgroup\$
  • \$\begingroup\$ For the odd number of passes case, you could swap pairs of elements in place, and then start the merge process with run size = 2, which end up with an even number of passes. \$\endgroup\$ – rcgldr Jan 28 '18 at 16:01
3
\$\begingroup\$

Your code looks amazing. That said, I recommend avoiding the use of raw Threads. It's better to make use of thread pools. Seeing as merge-sort is a naturally recursive algorithm, the use of a fork/join ExecutorService seems fitting.

Basically, by using raw Threads, you might get a slight performance gain, but it's too easy for your code to bloat. You have two rather large files in order to perform your sort, but by using the thread pool, I was able to implement it in one notably smaller file like so:

public static <T extends Comparable<? super T>> void sort(T[] array) {
    sort2(array, 0, array.length);
}

public static <T extends Comparable<? super T>> void sort(T[] array,
                                                          int fromIndex,
                                                          int toIndex) {
    ForkJoinPool pool = new ForkJoinPool();
    pool.invoke(new MergeAction<>(array, fromIndex, toIndex));
}

private static class MergeAction<T extends Comparable<? super T>> extends RecursiveAction {
    private static final int NON_PARALLEL_SORT_LENGTH = 100_000;

    private T[] array;
    private int fromIndex;
    private int toIndex;

    MergeAction(T[] array, int fromIndex, int toIndex) {
        this.array = array;
        this.fromIndex = fromIndex;
        this.toIndex = toIndex;
    }

    @Override
    protected void compute() {
        int rangeLength = toIndex - fromIndex;

        if (rangeLength < NON_PARALLEL_SORT_LENGTH) {
            // You might call this cheating, but if you continue going
            // smaller and smaller, you get an exponential amount of
            // new MergeActions, which makes the code slower. The sort
            // still works if you instead have the if statement be
            // if (rangeLength <= 1) return;
            Arrays.sort(array, fromIndex, toIndex);
            return;
        }

        int splitIndex = fromIndex + rangeLength / 2;

        invokeAll(new MergeAction<>(array, fromIndex, splitIndex), new MergeAction<>(array, splitIndex, toIndex));
        merge(fromIndex, splitIndex, toIndex);
    }

    private void merge(int from, int endFirst, int to) {
        Object[] newArray = new Object[to - from];
        int index = 0;

        int leftIndex = from;
        int rightIndex = endFirst;

        while (leftIndex < endFirst && rightIndex < to) {
            T left = array[leftIndex];
            T right = array[rightIndex];

            // left <= right
            if (left.compareTo(right) <= 0) {
                newArray[index] = array[leftIndex];
                leftIndex++;
            } else {
                newArray[index] = array[rightIndex];
                rightIndex++;
            }
            index++;
        }

        if (leftIndex < endFirst) {
            System.arraycopy(array, leftIndex, newArray, index, endFirst - leftIndex);
        } else if (rightIndex < to) {
            System.arraycopy(array, rightIndex, newArray, index, to - rightIndex);
        }

        System.arraycopy(newArray, 0, array, from, newArray.length);
    }
}

Running your demo pretty consistently has this version taking about 100 to 200 ms longer than your version (for about 2900 ms in your version).


However, this version naively creates a new array for every merge. If we instead create a second array at the beginning and simply shuffle data back and forth between arrays, it becomes faster than yours by about 100 to 200 ms on average, and it sometimes reaches the speed of Arrays.parallelSort():

public static <T extends Comparable<? super T>> void sort(T[] array) {
    sort(array, Comparator.naturalOrder());
}

public static <T> void sort(T[] array, Comparator<T> cmp) {
    sort(array, 0, array.length, cmp);
}

public static <T extends Comparable<? super T>> void sort(T[] array,
                                                           int fromIndex,
                                                           int toIndex) {
    sort(array, fromIndex, toIndex, Comparator.naturalOrder());
}

public static <T> void sort(T[] array,
                             int fromIndex,
                             int toIndex,
                             Comparator<T> cmp) {
    ForkJoinPool pool = new ForkJoinPool();
    final Object[] copy = new Object[array.length];
    final MergeSortAction<T> task = new MergeSortAction<>(array, copy, fromIndex, toIndex, cmp);
    pool.invoke(task);
    if (!task.getRawResult()) {
        System.arraycopy(copy, 0, array, 0, copy.length);
    }
}

private static class MergeSortAction<T> extends RecursiveTask<Boolean> {
    private static final int NON_PARALLEL_SORT_LENGTH = 100_000;

    private T[] array;
    private Object[] copy;
    private int fromIndex;
    private int toIndex;
    private Comparator cmp;

    MergeSortAction(T[] array, Object[] copy, int fromIndex, int toIndex, Comparator cmp) {
        this.array = array;
        this.copy = copy;
        this.fromIndex = fromIndex;
        this.toIndex = toIndex;
        this.cmp = cmp;
    }

    @Override
    protected Boolean compute() {
        int rangeLength = toIndex - fromIndex;

        if (rangeLength < NON_PARALLEL_SORT_LENGTH) {
            computeDirectly();
            return true;
        }

        int splitIndex = fromIndex + rangeLength / 2;

        final MergeSortAction mergeLeft = new MergeSortAction<>(array, copy, fromIndex, splitIndex, cmp);
        final MergeSortAction mergeRight = new MergeSortAction<>(array, copy, splitIndex, toIndex, cmp);
        invokeAll(mergeLeft, mergeRight);

        final boolean mergeRightResult = (boolean) mergeRight.getRawResult();

        merge(fromIndex, splitIndex, toIndex, mergeRightResult);
        return !mergeRightResult;
    }

    private Object[] chooseArray(boolean chooseCopy) {
        return chooseCopy ? copy : array;
    }

    private void computeDirectly() {
        Arrays.sort(array, fromIndex, toIndex);
    }

    @SuppressWarnings("unchecked")
    private void merge(int from, int endFirst, int to, boolean mergeToCopy) {
        Object[] src = chooseArray(!mergeToCopy);
        Object[] dest = chooseArray(mergeToCopy);
        int index = from;

        int leftIndex = from;
        int rightIndex = endFirst;

        while (leftIndex < endFirst && rightIndex < to) {
            Object left = src[leftIndex];
            Object right = src[rightIndex];

            // left <= right
            if (cmp.compare(left, right) <= 0) {
                dest[index] = src[leftIndex];
                leftIndex++;
            } else {
                dest[index] = src[rightIndex];
                rightIndex++;
            }
            index++;
        }

        if (leftIndex < endFirst) {
            System.arraycopy(src, leftIndex, dest, index, endFirst - leftIndex);
        } else if (rightIndex < to) {
            System.arraycopy(src, rightIndex, dest, index, to - rightIndex);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Seems his goal was performance, so whilst your review is nice, it's not very useful. The entire point seemed like it was trying to beat the built-in... \$\endgroup\$ – Pimgd Jun 28 '16 at 9:38
  • 1
    \$\begingroup\$ @Pimgd I disagree that my review is not useful. Yes, he asked for a review of performance, but I was under the impression that I was allowed to give other reviews as well. In this case, I was suggesting an alternate implementation that is more maintainable in the long run, which I believe to be a useful answer. \$\endgroup\$ – Justin Jun 28 '16 at 9:40
  • \$\begingroup\$ How should I put it? It's theoretically useful, but the practical useful answer is "Since your version is slower, you should use the built-in." That'd be one line of code which is far more maintainable AND faster. \$\endgroup\$ – Pimgd Jun 28 '16 at 9:41
  • \$\begingroup\$ @Pimgd I understand this. My point is that at some point you want to implement algorithms for which there is no built in version. But when you multi-thread them, it tends to be better to avoid raw threads \$\endgroup\$ – Justin Jun 28 '16 at 9:43
  • \$\begingroup\$ Nice adjustment! \$\endgroup\$ – Pimgd Jun 28 '16 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.