See the previous and initial iteration.I got rid of Run objects and just maintain two integer arrays in the RunHeap: one for starting indices, and another for ending indices. Also, thanks to a great suggestion by @maaartinus, the algorithm is now stable. The last, but not least: I do not longer sift up a newly pushed run as soon it is added, but rather append it to the tail of the array, and once all runs are considered, I do a bulk heapify, which (according to Introduction to Algorithms) runs in \$\Theta(N)\$ time instead of \$\Theta(N \log N)\$, which is an improvement.HeapSelectionSort.java:package net.coderodde.util.sorting;import java.util.Arrays;import java.util.Comparator;/** * This class implements a sorting algorithm called  * <b><i>heap selection sort</i></b>. The worst case complexity is linearithmic * O(n log n), best case complexity linear O(n). Linear space complexity and is * now <b>stable</b>. *  * @author Rodion rodde Efremov * @version 1.61 */public class HeapSelectionSort {    /**     * Sorts the range {@code array[fromIndex], array[fromIndex + 1], ...,     * array[toIndex - 2], array[toIndex - 1]} using the specified comparator.     *      * @param <T>        the array component type.     * @param array      the array holding the range to sort.     * @param fromIndex  the starting (inclusive) index of the range to sort.     * @param toIndex    the ending (exclusive) index of the range to sort.     * @param comparator the array component comparator.     */    public static <T> void sort(T[] array,                                 int fromIndex,                                 int toIndex,                                 Comparator<? super T> comparator) {        rangeCheck(array.length, fromIndex, toIndex);        if (toIndex - fromIndex < 2) {            return;        }        T[] aux = Arrays.copyOfRange(array, fromIndex, toIndex);        RunHeap<T> heap = createRunHeap(aux, comparator);        for (; fromIndex < toIndex; ++fromIndex) {            array[fromIndex] = heap.popElement();        }    }    /**     * Sorts the entire array using the specified comparator.     *      * @param <T>        the array component type.     * @param array      the array holding the range to sort.     * @param comparator the array component comparator.     */    public static <T> void sort(T[] array, Comparator<? super T> comparator) {        sort(array, 0, array.length, comparator);    }    /**     * Sorts the range {@code array[fromIndex], array[fromIndex + 1], ...,     * array[toIndex - 2], array[toIndex - 1]} using the natural comparator.     *      * @param <T>        the array component type.     * @param array      the array holding the range to sort.     * @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> void sort(T[] array, int fromIndex, int toIndex) {        sort(array, fromIndex, toIndex, NaturalOrder.INSTANCE);    }    /**     * Sorts the entire array using the natural comparator.     *      * @param <T>        the array component type.     * @param array      the array holding the range to sort.     */    public static <T> void sort(T[] array) {        sort(array, 0, array.length);    }    /**     * Builds the actual run heap. A run is any contiguous subsequence that is     * either ascending or (strictly) descending. We need descending runs to be     * strictly descending because we will reverse them in order. Thus, if we     * ever had contiguous equal elements, they would have been reversed and      * stability gone.     *      * @param <T>        the array component type.     * @param array      the actual array.     * @param comparator the comparator.     * @return the run heap.     */    private static <T> RunHeap<T>         createRunHeap(T[] array, Comparator<? super T> comparator) {        RunHeap<T> heap = new RunHeap<>(array, comparator);        int head;        int left = 0;        int last = array.length - 1;        while (left < last) {            head = left;            // Decide the direction of the next run.            if (comparator.compare(array[left], array[left + 1]) <= 0) {                ++left;                // Scanning ascending run.                while (left < last                        && comparator.compare(array[left],                                               array[left + 1]) <= 0) {                    ++left;                }                heap.pushRun(head, left);            } else {                // Scanning strictly descending run.                while (left < last                        && comparator.compare(array[left],                                               array[left + 1]) > 0) {                    ++left;                }                reverseRun(array, head, left);                heap.pushRun(head, left);            }            ++left;        }        // A special case: the very last element may be left without buddies        // so make it (the only) 1-element run.        if (left == last) {            heap.pushRun(left, left);        }        // Heapify. O(N) as described in Introduction to Algorithms.        heap.buildHeap();        return heap;    }    /**     * This class implements the actual run heap.     *      * @param <T> the array component type.     */    private static class RunHeap<T> {        private int size;        private final T[] array;        private final int[] fromIndexArray;        private final int[] toIndexArray;        private final Comparator<? super T> comparator;        RunHeap(T[] array, Comparator<? super T> comparator) {            this.array = array;            this.fromIndexArray = new int[array.length / 2 + 1];            this.toIndexArray = new int[array.length / 2 + 1];            this.comparator = comparator;        }        /**         * Removes and returns the minimal element.         *          * @return the minimal element.         */        T popElement() {            T ret = array[fromIndexArray[0]];            if (fromIndexArray[0] == toIndexArray[0]) {                // The topmost run is exhausted.                int last = fromIndexArray[--size];                fromIndexArray[0] = last;                last = toIndexArray[size];                toIndexArray[0] = last;            } else {                // Increment to the next element.                fromIndexArray[0]++;            }            // Possibly sift down the top element in order to restore the            // heap invariant.            siftDown(0);            return ret;        }        /**         * Appends the run to the tail of this heap.         *          * @param fromIndex the starting inclusive index of a run.         * @param toIndex   the ending inclusive index of a run.         */        void pushRun(int fromIndex, int toIndex) {            int nodeIndex = size++;            fromIndexArray[nodeIndex] = fromIndex;            toIndexArray[nodeIndex] = toIndex;        }        /**         * Heapifies the entire heap run, restoring the heap property. Runs in         * O(N) time, where N is the amount of runs.         */        void buildHeap() {            for (int i = size / 2; i >= 0; --i) {                siftDown(i);            }        }        private boolean isLessThan(int runIndex1, int runIndex2) {            T element1 = array[fromIndexArray[runIndex1]];            T element2 = array[fromIndexArray[runIndex2]];            int cmp = comparator.compare(element1, element2);            if (cmp != 0) {                return cmp < 0;            }            return fromIndexArray[runIndex1] < fromIndexArray[runIndex2];        }        private void siftDown(int index) {            int nodeIndex = index;            int leftChildIndex = (index << 1) + 1;            int rightChildIndex = leftChildIndex + 1;            int minIndex = index;            for (;;) {                if (leftChildIndex < size                         && isLessThan(leftChildIndex, nodeIndex)) {                    minIndex = leftChildIndex;                }                if (rightChildIndex < size                        && isLessThan(rightChildIndex, minIndex)) {                    minIndex = rightChildIndex;                }                if (minIndex == nodeIndex) {                    return;                }                int tmp = fromIndexArray[minIndex];                fromIndexArray[minIndex] = fromIndexArray[nodeIndex];                fromIndexArray[nodeIndex] = tmp;                tmp = toIndexArray[minIndex];                toIndexArray[minIndex] = toIndexArray[nodeIndex];                toIndexArray[nodeIndex] = tmp;                nodeIndex = minIndex;                leftChildIndex = (nodeIndex << 1) + 1;                rightChildIndex = leftChildIndex + 1;            }        }    }    private static <T> void reverseRun(T[] array, int fromIndex, int toIndex) {        for (; fromIndex < toIndex; ++fromIndex, --toIndex) {            T tmp = array[fromIndex];            array[fromIndex] = array[toIndex];            array[toIndex] = tmp;        }    }    private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {        if (fromIndex > toIndex) {            throw new IllegalArgumentException(                    fromIndex( + fromIndex + ) > toIndex( + 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);        }    }    private static final class NaturalOrder implements Comparator<Object> {        @SuppressWarnings(unchecked)        @Override        public int compare(Object first, Object second) {            return ((Comparable<Object>) first).compareTo(second);        }        private static final NaturalOrder INSTANCE = new NaturalOrder();    }}Demo.java:package net.coderodde.util.sorting;import java.util.Arrays;import java.util.Random;import static net.coderodde.util.sorting.HeapSelectionSort.sort;public class Demo {    public static void main(final String... args) {        demo();    }    private static Integer[] createRandomIntegerArray(int size, Random random) {        Integer[] ret = new Integer[size];        for (int i = 0; i < size; ++i) {            ret[i] = random.nextInt(size / 2);        }        return ret;    }    private static Integer[] createPresortedArray(int size,                                                   int runs,                                                   Random random) {        Integer[] ret = createRandomIntegerArray(size, random);        int runLength = size / runs;        for (int i = 0; i < runs; ++i) {            Arrays.sort(ret, runLength * i,                         Math.min(size, runLength * (i + 1)));        }        return ret;    }    private static boolean isSorted(Integer[] 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;    }    private static boolean isSorted(Integer[] array) {        return isSorted(array, 0, array.length);    }    private static <T> boolean arraysEqual(T[] array1, T[] array2) {        if (array1.length != array2.length) {            return false;        }        for (int i = 0; i < array1.length; ++i) {            if (array1[i] != array2[i]) {                return false;            }        }        return true;    }        private static void demo() {        long arraysSortTotal = 0L;        long heapSelectionSortTotal = 0L;        long seed = 3706213852107L; System.nanoTime();        System.out.println(Seed:  + seed);        System.out.println(-------------------);        for (int op = 0; op < 10; ++op) {            Random random = new Random(System.nanoTime());            Integer[] array1 = createRandomIntegerArray(100000, random);            Integer[] array2 = array1.clone();            long ta = System.currentTimeMillis();            Arrays.sort(array1);            long tb = System.currentTimeMillis();            System.out.println(Random array:);            System.out.println(Arrays.sort in  + (tb - ta) +  ms, sorted:  +                               isSorted(array1));            arraysSortTotal += tb - ta;            ta = System.currentTimeMillis();            sort(array2);            tb = System.currentTimeMillis();            heapSelectionSortTotal += tb - ta;            System.out.println(Heap insertion sort in  + (tb - ta) +  ms,  +                               sorted:  + isSorted(array2));            System.out.println(Arrays same:  + arraysEqual(array1, array2));            for (int i = 0; i < 80; ++i) {                System.out.print(-);            }            System.out.println();            array1 = createPresortedArray(150000, 100, random);            array2 = array1.clone();            ta = System.currentTimeMillis();            Arrays.sort(array1);            tb = System.currentTimeMillis();            System.out.println(Presorted array:);            System.out.println(Arrays.sort in  + (tb - ta) +  ms, sorted:  +                               isSorted(array1));            arraysSortTotal += tb - ta;            ta = System.currentTimeMillis();            sort(array2);            tb = System.currentTimeMillis();            heapSelectionSortTotal += tb - ta;            System.out.println(Heap insertion sort in  + (tb - ta) +  ms,  +                               sorted:  + isSorted(array2));            System.out.println(Arrays same:  + arraysEqual(array1, array2));            for (int i = 0; i < 80; ++i) {                System.out.print(-);            }            System.out.println();        }        System.out.println(Total of Arrays.sort:  + arraysSortTotal +  ms.);        System.out.println(Total of heap insertion sort:  +                            heapSelectionSortTotal +  ms.);    }}Digits I got: Seed: 3706213852107 ------------------- Random array: Arrays.sort in 222 ms, sorted: true Heap insertion sort in 148 ms, sorted: true Arrays identical: true ------------------- Presorted array: Arrays.sort in 183 ms, sorted: true Heap insertion sort in 91 ms, sorted: true Arrays identical: true ------------------- Random array: Arrays.sort in 33 ms, sorted: true Heap insertion sort in 109 ms, sorted: true Arrays identical: true ------------------- Presorted array: Arrays.sort in 30 ms, sorted: true Heap insertion sort in 57 ms, sorted: true Arrays identical: true ------------------- Random array: Arrays.sort in 44 ms, sorted: true Heap insertion sort in 108 ms, sorted: true Arrays identical: true ------------------ Presorted array: Arrays.sort in 46 ms, sorted: true Heap insertion sort in 39 ms, sorted: true Arrays identical: true ------------------- Random array: Arrays.sort in 53 ms, sorted: true Heap insertion sort in 95 ms, sorted: true Arrays identical: true ------------------- Presorted array: Arrays.sort in 29 ms, sorted: true Heap insertion sort in 73 ms, sorted: true Arrays identical: true ------------------- Random array: Arrays.sort in 33 ms, sorted: true Heap insertion sort in 111 ms, sorted: true Arrays identical: true ------------------- Presorted array: Arrays.sort in 29 ms, sorted: true Heap insertion sort in 58 ms, sorted: true Arrays identical: true ------------------- Random array: Arrays.sort in 42 ms, sorted: true Heap insertion sort in 68 ms, sorted: true Arrays identical: true ------------------- Presorted array: Arrays.sort in 31 ms, sorted: true Heap insertion sort in 35 ms, sorted: true Arrays identical: true ------------------- Random array: Arrays.sort in 35 ms, sorted: true Heap insertion sort in 70 ms, sorted: true Arrays identical: true ------------------- Presorted array: Arrays.sort in 34 ms, sorted: true Heap insertion sort in 36 ms, sorted: true Arrays identical: true ------------------- Random array: Arrays.sort in 32 ms, sorted: true Heap insertion sort in 71 ms, sorted: true Arrays identical: true ------------------- Presorted array: Arrays.sort in 30 ms, sorted: true Heap insertion sort in 38 ms, sorted: true Arrays identical: true ------------------- Random array: Arrays.sort in 35 ms, sorted: true Heap insertion sort in 114 ms, sorted: true Arrays identical: true ------------------- Presorted array: Arrays.sort in 29 ms, sorted: true Heap insertion sort in 39 ms, sorted: true Arrays identical: true ------------------- Random array: Arrays.sort in 32 ms, sorted: true Heap insertion sort in 81 ms, sorted: true Arrays identical: true ------------------- Presorted array: Arrays.sort in 35 ms, sorted: true Heap insertion sort in 42 ms, sorted: true Arrays identical: true ------------------- Total of Arrays.sort: 1037 ms. Total of heap insertion sort: 1483 ms.
Heap selection sort - follow-up
java;algorithm;sorting;heap