I plan to work on Introsort, which requires a working implementation of heap sort. Also, the heap sort implementation must be able to sort arbitrary ranges within an array, which, in turn, requires some more involved index manipulation.Heapsort.java:package net.coderodde.util.sorting;/** * This class implements heap sort. *  * @author Rodion rodde Efremov * @version 1.6 */public class Heapsort {    /**     * Sorts the entire integer array.     *      * @param array the array to sort.     */    public static void sort(int[] array) {        sort(array, 0, array.length);    }    /**     * Sorts a particular range {@code array[fromIndex], array[fromIndex + 1],      * ..., array[toIndex - 2], array[toIndex - 1]}.     *      * @param array     the array containing the target range.     * @param fromIndex the starting, inclusive index of the target range.     * @param toIndex   the ending, exclusive index of the target range.     */    public static void sort(int[] array, int fromIndex, int toIndex) {        if (toIndex - fromIndex < 2) {            return;        }        // CLRS says 'BUILD-MAX-HEAP' is O(n).        buildMaxHeap(array, fromIndex, toIndex);        // And this is O(n log n).        for (int i = toIndex - 1; i > fromIndex; --i) {            int tmp = array[i];            array[i] = array[fromIndex];            array[fromIndex] = tmp;            maxSiftDown(array, fromIndex, i, 0);        }    }    /**     * Makes sure the range {@code array[fromIndex], array[fromIndex + 1], ...,     * array[toIndex - 2], array[toIndex - 1]} forms a maximum heap.     *      * @param array     the array holding the target range.     * @param fromIndex the starting, inclusive index of the range to rebuild     *                  as a heap.     * @param toIndex   the ending, exclusive index of the range to rebuild as      *                  a heap.     */    private static void buildMaxHeap(int[] array, int fromIndex, int toIndex) {        int rangeLength = toIndex - fromIndex;        for (int i = rangeLength / 2; i >= 0; --i) {            maxSiftDown(array, fromIndex, toIndex, i);        }    }    /**     * Sifts down the element {@code array[index]} in order to restore the max     * heap property. The heap is assumed to occupy the range      * {@code array[fromIndex ... toIndex - 1]}.     *      * @param array     the array holding the heap.     * @param fromIndex the starting, inclusive index of the heap.     * @param toIndex   the ending, exclusive index of the heap.     * @param index     the index of the element to sift down.     */    private static void maxSiftDown(int[] array,                                     int fromIndex,                                     int toIndex,                                    int index) {        int leftChildIndex = left(index);        // Right child index is one position from left child index towards         // larger indices.        int rightChildIndex = leftChildIndex + 1;        int maxChildIndex = index;        // Save the array component we want to sift down.        int target = array[fromIndex + index];        for (;;) {            if (fromIndex + leftChildIndex < toIndex                     && array[fromIndex + leftChildIndex] > target) {                maxChildIndex = leftChildIndex;            }            if (maxChildIndex == index) {                if (fromIndex + rightChildIndex < toIndex                        && array[fromIndex + rightChildIndex] > target) {                    maxChildIndex = rightChildIndex;                }            } else {                if (fromIndex + rightChildIndex < toIndex                        && array[fromIndex + rightChildIndex] >                            array[fromIndex + leftChildIndex]) {                    maxChildIndex = rightChildIndex;                }            }            if (maxChildIndex == index) {                // No swap. Just insert the sifted element.                array[fromIndex + maxChildIndex] = target;                return;            }            // No swap here neither.             // Just move up the maximum to current position.            array[fromIndex + index] = array[fromIndex + maxChildIndex];            index = maxChildIndex;            leftChildIndex = left(index);            rightChildIndex = leftChildIndex + 1;        }    }    /**     * Returns the index of the left child of the element at index      * {@code index}.     *      * @param index the index of the target element.     * @return the index of the left child of the target element.     */    private static int left(int index) {        return (index << 1) + 1;    }}Demo.java:import java.util.Arrays;import java.util.Random;import java.util.stream.IntStream;import net.coderodde.util.sorting.Heapsort;/** * This class implements a demonstration of Introsort's and heap sort's  * performance as compared to {@link java.util.Arrays.sort}. *  * @author Rodion rodde Efremov * @version 1.6 */public class Demo {    private static final int LENGTH = 500000;    private static final int ITERATIONS = 30;    public static void main(String[] args) {        long seed = System.currentTimeMillis();        Random random = new Random(seed);        long totalArraysSort = 0L;        long totalHeapsort = 0L;        System.out.println(Seed:  + seed);        for (int iteration = 0; iteration < ITERATIONS; ++iteration) {            int[] array1 = getRandomIntegerArray(LENGTH, random);            int[] array2 = array1.clone();            int fromIndex = random.nextInt(LENGTH / 10);            int toIndex = LENGTH - random.nextInt(LENGTH / 10);            long startTime = System.currentTimeMillis();            Arrays.sort(array1, fromIndex, toIndex);            long endTime = System.currentTimeMillis();            totalArraysSort += endTime - startTime;            System.out.println(Arrays.sort in  + (endTime - startTime) +                                 milliseconds.);            startTime = System.currentTimeMillis();            Heapsort.sort(array2, fromIndex, toIndex);            endTime = System.currentTimeMillis();            totalHeapsort += endTime - startTime;            System.out.println(Heapsort.sort in  + (endTime - startTime) +                                 milliseconds);            System.out.println(Arrays identical:  + Arrays.equals(array1,                                                                     array2));            System.out.println(---);        }        System.out.println(Total Arrays.sort time:    + totalArraysSort +                             milliseconds.);        System.out.println(Total Heapsort.sort time:  + totalHeapsort +                            milliseconds.);    }    private static int[] getRandomIntegerArray(int size, Random random) {        return IntStream.range(0, size)                        .map((i) -> random.nextInt(2 * size))                        .toArray();    }}After I run the Demo, it prints:Total Arrays.sort time:   1929 milliseconds.Total Heapsort.sort time: 3588 milliseconds.Slower, but no can do. Hopefully introsort may come closer.
Heapsort for arbitrary ranges in Java
java;sorting;heap