See the next iteration.
I designed and implemented this adaptive heap sort in Java. It works as follows:
- Copy the range to be sorted into auxiliary array \$A\$
- Create an empty run heap \$H\$
- Scan \$A\$ from beginning to the end and whenever we have counted a longest possible run (a run is a longest ascending or descending contiguous subsequence of the input sequence), we store it in \$H\$.
Each run \$r\$ is encoded by two integers: \$r.from\$ is the index of the first array component in the run, and \$r.to\$ is the index of the last array component in the run. In the run heap, the top element is the run \$r\$, for which \$A[r.from]\$ is minimal (notice the indirection). - Then, as long as the run heap is not empty, we remove the top element. This is done by returning \$A[r.from]\$, where \$r\$ is the topmost run in the run heap. After that, we set \$r.from \leftarrow r.from + 1\$, and possibly sift it down in order to restore the indirect heap invariant. If a run is exhausted, it is removed from the heap.
The best case complexity of this sort is \$\Theta(N)\$. The worst case complexity is \$\Theta(N \log N)\$. Linear space complexity and is unstable (may reorder the equal elements) due to heap structure.
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
* unstable.
*
* @author Rodion "rodde" Efremov
* @version 1.6
*/
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);
Heap<T> heap = createHeap(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);
}
private static <T> Heap<T> createHeap(T[] array,
Comparator<? super T> comparator) {
Heap<T> heap = new Heap<>(array.length / 2 + 1, array, comparator);
int head;
int left = 0;
int right = 1;
int last = array.length - 1;
while (left < last) {
head = left;
// Decide the direction of the next run.
if (comparator.compare(array[left++], array[right++]) <= 0) {
// Scanning ascending run.
while (left < last
&& comparator.compare(array[left], array[right]) <= 0) {
++left;
++right;
}
heap.pushRun(new Run(head, left));
} else {
// Scanning descending run.
while (left < last
&& comparator.compare(array[left], array[right]) >= 0) {
++left;
++right;
}
Run run = new Run(head, left);
reverseRun(array, run);
heap.pushRun(run);
}
++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) {
heap.pushRun(new Run(left, left));
}
return heap;
}
private static class Run {
int from;
int to;
Run(int from, int to) {
this.from = from;
this.to = to;
}
}
private static class Heap<T> {
private int size;
private final T[] array;
private final Run[] runs;
private final Comparator<? super T> comparator;
Heap(int size, T[] array, Comparator<? super T> comparator) {
this.runs = new Run[size];
this.array = array;
this.comparator = comparator;
}
T popElement() {
T ret = array[runs[0].from];
if (runs[0].from == runs[0].to) {
// The run at the head of the heap is fully processed, remove.
Run last = runs[--size];
runs[0] = last;
} else {
// Increment to the next element.
++runs[0].from;
}
// Possibly sift down the top element in order to restore the
// heap invariant.
siftDown();
return ret;
}
void pushRun(Run run) {
int nodeIndex = size++;
runs[nodeIndex] = run;
siftUp(nodeIndex);
}
void siftUp(int index) {
Run target = runs[index];
for (;;) {
int parentIndex = (index - 1) >> 1;
if (parentIndex < 0) {
runs[0] = target;
return;
}
if (comparator.compare(array[runs[parentIndex].from],
array[target.from]) > 0) {
runs[index] = runs[parentIndex];
index = parentIndex;
} else {
runs[index] = target;
return;
}
}
}
private void siftDown() {
int nodeIndex = 0;
int leftChildIndex = 1;
int rightChildIndex = 2;
int minIndex = 0;
for (;;) {
if (leftChildIndex < size
&& comparator.compare(array[runs[leftChildIndex].from],
array[runs[nodeIndex].from]) < 0) {
minIndex = leftChildIndex;
}
if (rightChildIndex < size
&& comparator.compare(array[runs[rightChildIndex].from],
array[runs[minIndex].from]) < 0) {
minIndex = rightChildIndex;
}
if (minIndex == nodeIndex) {
return;
}
Run run = runs[minIndex];
runs[minIndex] = runs[nodeIndex];
runs[nodeIndex] = run;
nodeIndex = minIndex;
leftChildIndex = (nodeIndex << 1) + 1;
rightChildIndex = leftChildIndex + 1;
}
}
}
private static <T> void reverseRun(T[] array, Run run) {
for (int i = run.from, j = run.to; i < j; ++i, --j) {
T tmp = array[i];
array[i] = array[j];
array[j] = 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.Objects;
import java.util.Random;
import static net.coderodde.util.sorting.HeapSelectionSort.sort;
public class Demo {
public static void main(final String... args) {
int size = 500000;
long seed = System.currentTimeMillis();
Random random = new Random(seed);
Integer[] array1 = createRandomIntegerArray(size, random);
Integer[] array2 = array1.clone();
System.out.println("Seed: " + seed);
int fromIndex = 2;
int toIndex = size - 2;
//// Random arrays.
System.out.println("--- Random integer array ---");
long ta = System.currentTimeMillis();
Arrays.sort(array1, fromIndex, toIndex, Integer::compare);
long tb = System.currentTimeMillis();
System.out.println("java.util.Arrays.sort in " + (tb - ta) +
" ms. Sorted: " +
isSorted(array1, fromIndex, toIndex));
ta = System.currentTimeMillis();
sort(array2, fromIndex, toIndex, Integer::compare);
tb = System.currentTimeMillis();
System.out.println("Heap selection sort in " + (tb - ta) +
" ms. Sorted: " +
isSorted(array2, fromIndex, toIndex));
System.out.println("Array contents same: " + arraysEqual(array1,
array2));
// Presorted arrays.
array1 = createPresortedArray(size, 23);
array2 = array1.clone();
System.out.println("--- Presorted array ---");
ta = System.currentTimeMillis();
Arrays.sort(array1, fromIndex, toIndex, Integer::compare);
tb = System.currentTimeMillis();
System.out.println("java.util.Arrays.sort in " + (tb - ta) +
" ms. Sorted: " +
isSorted(array1, fromIndex, toIndex));
ta = System.currentTimeMillis();
sort(array2, fromIndex, toIndex, Integer::compare);
tb = System.currentTimeMillis();
System.out.println("Heap selection sort in " + (tb - ta) +
" ms. Sorted: " +
isSorted(array2, fromIndex, toIndex));
System.out.println("Array contents same: " + arraysEqual(array1,
array2));
}
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) {
Integer[] ret = createRandomIntegerArray(size, new 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 <T> boolean arraysEqual(T[] array1, T[] array2) {
if (array1.length != array2.length) {
return false;
}
for (int i = 0; i < array1.length; ++i) {
if (!Objects.equals(array1[i], array2[i])) {
return false;
}
}
return true;
}
}
So, what do you think?
Have you seen this algorithm discussed in computer scientific literature?
