I'm afraid maaartinus is right about the odds to improve on the state of the art in sorting in his comment to his answer to the initial iteration.
With runs at most half as numerous as elements, the heap stays smaller - a bit. The number of operations doesn't decrease as much, as runs need to be re-sifted.
If you declare the "non-Comparator-sorts" using <T extends Comparable<T>>, you can use Comparator.naturalOrder() (rendering class NaturalOrder dispensable) - you're casting, anyway.
I tried to reduce code multiplication in createRunHeap - not entirely successful:
for ( ; left < last ; left++) {
final int head = left;
// Decide the direction of the next run.
final boolean strictlyDecreasing =
comparator.compare(array[left++], array[left]) < 0;
while (left < last
&& strictlyDecreasing
== comparator.compare(array[left++], array[left]) < 0) {
}
// reversing strictly decreasing runs, only
// keeps forming runs stable while increasing run count
// by two for every run of "equal" elements
// wedged between two strictly decreasing runs
if (strictlyDecreasing) {
reverseRun(array, head, left);
}
heap.pushRun(head, left);
}
But, then,
/** Detects changes in parameter value to the one used
* in the constructor or first invocation, respectively */
static class ChangeDetector {
boolean set;
Object previous;
/** Will detect changes
* from the parameter of the first invocation */
ChangeDetector(){}
/** Will detect changes from {@code initial} */
ChangeDetector(Object initial) {
previous = initial;
set = true;
}
/** @return {@code thisTime}
* equals parameter in constructor/first invocation */
boolean same(Object thisTime) {
if (!set) {
previous = thisTime;
return set = true;
}
return previous == thisTime
|| previous != null && previous.equals(thisTime);
}
}
…
for ( ; left < last ; left++) {
final int head = left;
// Decide the direction of the next run.
ChangeDetector stays = new ChangeDetector();
while (left < last
&& stays.same(comparator.compare(
array[left++], array[left]) < 0)) {
}
if (stays.same(Boolean.TRUE)) {
reverseRun(array, head, left);
}
heap.pushRun(head, left);
}
