See the the previous iteration.Now I refactored the code a bit so that I do not need to pass like 6 parameters to helper methods. Also, I did a small tweak that allows the sort to arrive to the state where the amount of runs is a power of two, which solves the orphan issue: suppose your data has \$1048577 = 2^{20} + 1\$ runs. Now normally you would sort the first \$2^{20}\$ runs, after which you would have to perform another large merge over the entire range in order to merge the last orphan run.Also, I ignored the generics and pass to my sort any object that implements Comparable. Now, what do you think?NaturalMergesort.java:package net.coderodde.util.sorting;import java.util.Arrays;/** * This class implements natural merge sort for {@code Comparable} objects. *  * @author Rodion rodde Efremov * @version 1.61 (Oct 1, 2015) */public final class NaturalMergesort {    private Object[] source;    private Object[] target;    private int sourceOffset;    private int targetOffset;    private UnsafeIntQueue queue;    private NaturalMergesort(Object[] array, int fromIndex, int toIndex) {        if (toIndex - fromIndex < 2) {            // Nothing to sort.            return;        }        this.queue = buildRunSizeQueue(array, fromIndex, toIndex);        Object[] buffer = Arrays.copyOfRange(array, fromIndex, toIndex);        int mergePasses = getPassAmount(queue.size());        if ((mergePasses & 1) == 1) {            // Odd amount of passes over the entire range; set the buffer array             // as source so that the sorted shit ends up in the original array.            source = buffer;            target = array;            sourceOffset = 0;            targetOffset = fromIndex;        } else {            // Arrange the stuff such that after the last merge pass all shit is            // in the argument array.            source = array;            target = buffer;            sourceOffset = fromIndex;            targetOffset = 0;        }        sort();    }    private void sort() {            // The amount of runs in current merge pass that were not processed yet.        int runsLeft = queue.size();        // The amount of elements processed from beginnig of the ranges.        int offset = 0;        // While there are runs to merge, do:        while (queue.size() > 1) {            if (runsLeft == 3) {                // We handle this special case in order to get fast to the state                // where the amount of remaining runs is a power of two. We do                 // this for the following reason: Suppose you have 1048577 =                // 1048576 + 1 = 2^(20) + 1 elements in the requested range.                // Now the algorithm would sort the first 2^(20) element AND                // will have to do one more merge pass just for putting the last                // orphan element to its correct position.                int leftRunLength = queue.dequeue();                int middleRunLength = queue.dequeue();                int rightRunLength = queue.dequeue();                merge(offset,                      leftRunLength,                      middleRunLength,                      rightRunLength);                queue.enqueue(leftRunLength +                              middleRunLength + rightRunLength);                int itmp = sourceOffset;                sourceOffset = targetOffset;                targetOffset = itmp;                Object[] tmp = source;                source = target;                target = tmp;                runsLeft = queue.size();                offset = 0;                continue;            }            int leftRunLength =  queue.dequeue();            int rightRunLength = queue.dequeue();            merge(offset,                  leftRunLength,                   rightRunLength);            // Bounce the run we obtained by merging the two runs to the tail.            queue.enqueue(leftRunLength + rightRunLength);            offset += leftRunLength + rightRunLength;            runsLeft -= 2;            if (runsLeft == 0) {                // Swap array offsets.                int itmp = sourceOffset;                sourceOffset = targetOffset;                targetOffset = itmp;                // Swap array roles.                Object[] tmp = source;                source = target;                target = tmp;                // Go to the beginning of the array.                runsLeft = queue.size();                offset = 0;            }        }    }    /**     * Sorts the entire input array.      *      * @param array the array to sort.     */    public static void sort(Object[] array) {        sort(array, 0, array.length);           }    /**     * Sorts a specific range in the input array.     *      * @param array     the array holding the target 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 void sort(Object[] array, int fromIndex, int toIndex) {        new NaturalMergesort(array, fromIndex, toIndex).sort();    }    /**     * Reverses the range <code>array[fromIndex ... toIndex - 1]</code>. Used      * for making descending runs ascending.     *      * @param array the array holding the desired range.     * @param fromIndex the least index of the range to reverse.     * @param toIndex the index one past the greatest index of the range.     */    public static void reverseRun(Object[] array,                                   int fromIndex,                                  int toIndex) {        for(int l = fromIndex, r = toIndex - 1; l < r; ++l, --r) {            Object tmp = array[l];            array[l] = array[r];            array[r] = tmp;        }    }    /**     * This method implements a 3-way merge operation.     *      * @param offset          the amount of elements to skip from the beginning     *                        of the ranges.     * @param leftRunLength   the length of the left run.     * @param middleRunLength the length of the middle run.     * @param rightRunLength  the length of the right run.     */    private void merge(int offset,                       int leftRunLength,                       int middleRunLength,                       int rightRunLength) {        int left = sourceOffset + offset;        int middle = left + leftRunLength;        int right = middle + middleRunLength;        int leftBound = middle;        int middleBound = right;        int rightBound = right + rightRunLength;        int placementOffset = targetOffset + offset;        while (left < leftBound && middle < middleBound && right < rightBound) {            Comparable cLeft   = (Comparable) source[left];            Comparable cMiddle = (Comparable) source[middle];            Comparable cRight  = (Comparable) source[right];            if (cRight.compareTo(cMiddle) < 0) {                // Here, cRight < cMiddle                if (cRight.compareTo(cLeft) < 0) {                    target[placementOffset++] = cRight;                    ++right;                } else {                    target[placementOffset++] = cLeft;                    ++left;                }            } else {                // Here, cMiddle <= cRight.                if (cLeft.compareTo(cMiddle) <= 0) {                    target[placementOffset++] = cLeft;                    ++left;                } else {                    target[placementOffset++] = cMiddle;                    ++middle;                }            }        }        while (left < leftBound && middle < middleBound) {            Comparable cLeft   = (Comparable) source[left];            Comparable cMiddle = (Comparable) source[middle];            target[placementOffset++] = cMiddle.compareTo(cLeft) < 0 ?                    source[middle++] :                    source[left++] ;        }        while (left < leftBound && right < rightBound) {            Comparable cLeft  = (Comparable) source[left];            Comparable cRight = (Comparable) source[right];            target[placementOffset++] = cRight.compareTo(cLeft) < 0 ?                    source[right++] :                    source[left++];        }        while (middle < middleBound && right < rightBound) {            Comparable cMiddle = (Comparable) source[middle];            Comparable cRight  = (Comparable) source[right];            target[placementOffset++] = cMiddle.compareTo(cRight) < 0 ?                    source[middle++] :                    source[right++];        }        System.arraycopy(source,                          left,                          target,                          placementOffset,                          leftBound - left);        System.arraycopy(source,                          middle,                          target,                          placementOffset,                          middleBound - middle);        System.arraycopy(source,                          right,                          target,                          placementOffset,                          rightBound - right);    }    /**     * This method implements the merging routine.     *      * @param offset         the amount of elements to skip from the beginning      *                       of each array.     * @param leftRunLength  the length of the left run.     * @param rightRunLength the length of the right run.     */    private void merge(int offset,                       int leftRunLength,                       int rightRunLength) {        int left = sourceOffset + offset;        int right = left + leftRunLength;        int leftBound = right;        int rightBound = right + rightRunLength;        int placementOffset = targetOffset + offset;        while (left < leftBound && right < rightBound) {            target[placementOffset++] =                    ((Comparable) source[right]).compareTo(source[left]) < 0 ?                                  source[right++] :                                  source[left++];        }        System.arraycopy(source,                          left,                          target,                          placementOffset,                          leftBound - left);        System.arraycopy(source,                          right,                          target,                          placementOffset,                          rightBound - right);    }    /**     * This class method returns the amount of merge passes over the input range     * needed to sort {@code runAmount} runs.     */    private static int getPassAmount(int runAmount) {        return 32 - Integer.numberOfLeadingZeros(runAmount / 2);    }    /**     * Scans the runs over the range {@code array[fromIndex .. toIndex - 1]} and      * returns a {@link UnsafeIntQueue} containing the sizes of scanned runs in      * the same order as they appear in the input range.     *      * @param array     the array containing the desired range.     * @param fromIndex the starting, inclusive index of the range to scan.     * @param toIndex   the ending, exclusive index of the range to scan.     *      * @return a {@code UnsafeIntQueue} describing the lengths of the runs in      * the input range.     */    static UnsafeIntQueue buildRunSizeQueue(Object[] array,                                             int fromIndex,                                            int toIndex) {        UnsafeIntQueue queue =           new UnsafeIntQueue(((toIndex - fromIndex) >>> 1) + 1);        int head;        int left = fromIndex;        int right = left + 1;        int last = toIndex - 1;        while (left < last) {            head = left;            // Decide the direction of the next run.            if (((Comparable) array[left++]).compareTo(array[right++]) <= 0) {                // Scan an ascending run.                while (left < last                        && ((Comparable) array[left])                              .compareTo(array[right]) <= 0) {                    ++left;                    ++right;                }                queue.enqueue(left - head + 1);            } else {                // Scan a strictly descending run.                while (left < last                        && ((Comparable) array[left])                              .compareTo(array[right]) > 0) {                    ++left;                    ++right;                }                queue.enqueue(left - head + 1);                // We reverse a strictly descending run as to minimize the                // the amount of runs scanned in total. Strictness is required.                reverseRun(array, head, right);            }            ++left;            ++right;        }        // A special case: the very last element may be left without buddies        // so make it (the only) 1-element run.        if (left == last) {            queue.enqueue(1);        }        return queue;    }    /**     * This is the implementation class for an array-based queue of integers. It      * sacrifices under- and overflow checks as to squeeze a little bit more of     * efficiency and thus is an ad-hoc data structure hidden from the client     * programmers.     *      * @author Rodion Efremov     * @version 2014.12.01     */    private static final class UnsafeIntQueue {        /**         * The minimum capacity of this queue.         */        private static final int MINIMUM_CAPACITY = 256;        /**         * Stores the actual elements.         */        private final int[] storage;        /**         * Points to the element that will be dequeued next.         */        private int head;        /**         * Points to the array component to which the next element will be          * inserted.         */        private int tail;        /**         * Caches the amount of elements stored.         */        private int size;        /**         * Used for faster head/tail updates.         */        private final int mask;        /**         * Creates an empty integer queue with capacity of the least power of         * two no less than original capacity value.         */        UnsafeIntQueue(int capacity) {            capacity = fixCapacity(capacity);            this.mask = capacity - 1;            this.storage = new int[capacity];        }        /**         * Appends an integer to the tail of this queue.         *          * @param num the integer to append.         */        void enqueue(int num) {            storage[tail & mask] = num;            tail = (tail + 1) & mask;            ++size;        }        /**         * Pops from the head of this queue an integer.         *          * @return the integer at the head of this queue.         */        int dequeue() {            int ret = storage[head];            head = (head + 1) & mask;            --size;            return ret;        }        /**         * Returns the amount of values stored in this queue.         */        int size() {            return size;        }        /**         * This routine is responsible for computing an integer that is a power         * of two no less than {@code capacity}.         */        private static int fixCapacity(int capacity) {            capacity = Math.max(capacity, MINIMUM_CAPACITY);            int ret = 1;            while (ret < capacity) {                ret <<= 1;            }            return ret;        }    }}Demo.java:import java.util.Arrays;import java.util.Random;import net.coderodde.util.sorting.NaturalMergesort;public class Demo {    private static final int ARRAY_LENGTH = 2000000;    private static final int FROM_INDEX = 5;    private static final int TO_INDEX = ARRAY_LENGTH - 6;    static int getPasses(int runs) {        return 32 - Integer.numberOfLeadingZeros(runs / 2);    }    public static void main(final String... args) {        long seed = System.currentTimeMillis();        System.out.println(Seed:  + seed);        System.out.println();        System.out.println(-- Random data demo --);        Random rnd = new Random(seed);        Integer[] array1 = getRandomIntegerArray(ARRAY_LENGTH,                                                  -10000,                                                  10000,                                                  rnd);        Integer[] array2 = array1.clone();        System.out.print(My natural merge sort:   );        long ta1 = System.currentTimeMillis();        NaturalMergesort.sort(array2, FROM_INDEX, TO_INDEX);        long tb1 = System.currentTimeMillis();        System.out.println((tb1 - ta1) +  ms.);        System.out.print(java.util.Arrays.sort(): );        long ta2 = System.currentTimeMillis();        java.util.Arrays.sort(array1, FROM_INDEX, TO_INDEX);        long tb2 = System.currentTimeMillis();        System.out.println((tb2 - ta2) +  ms.);        System.out.println(Sorted arrays equal:  +                Arrays.equals(array1, array2));        System.out.println();        ////        System.out.println(-- Presorted data demo --);        array1 = getPresortedIntegerArray(ARRAY_LENGTH);        array2 = array1.clone();        System.out.print(My natural merge sort:   );        ta1 = System.currentTimeMillis();        NaturalMergesort.sort(array2, FROM_INDEX, TO_INDEX);        tb1 = System.currentTimeMillis();        System.out.println((tb1 - ta1) +  ms.);        System.out.print(java.util.Arrays.sort(): );        ta2 = System.currentTimeMillis();        java.util.Arrays.sort(array1, FROM_INDEX, TO_INDEX);        tb2 = System.currentTimeMillis();        System.out.println((tb2 - ta2) +  ms.);        System.out.println(Sorted arrays equal:  +                 Arrays.equals(array1, array2));    }    private static Integer[] getRandomIntegerArray(final int size,                                                    final int min,                                                   final int max,                                                   final Random rnd) {        final Integer[] array = new Integer[size];        for (int i = 0; i < size; ++i) {            array[i] = rnd.nextInt(max - min + 1) + min;        }        return array;    }    private static Integer[] getPresortedIntegerArray(final int size) {        final Integer[] array = new Integer[size];        for (int i = 0; i < size; ++i) {            array[i] = i % (size / 8);        }        for (int i = 0, j = size - 1; i < j; ++i, --j) {            final Integer tmp = array[i];            array[i] = array[j];            array[j] = tmp;        }        return array;    }}
Natural merge sort in Java - follow-up 2
java;algorithm;sorting;mergesort