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.
