Natural merge sort in Java

Natural merge sort is a modification of merge sort that sacrifices \$\mathcal{O}(N)\$ to actually build a list of "runs" that may be defined as monotonically increasing or strictly decreasing contiguous subsequences in the input array. After the run queue is established, the algorithm repetitively pops two runs from the queue, merges the two, and pushes the resulting run to the tail of queue. The algorithm continues to merge pairwise until the queue contains only one run, which corresponds to the entire sorted range. The time complexity is \$\mathcal{O}(n \log m)\$, where \$n\$ is the length of the requested range \$R\$ and \$m\$ is the amount of runs in \$R\$.

Is this performance attitude and style reasonable?

Arrays.java:

```
package net.coderodde.util;

/**
* This class contains static methods implementing a natural merge sort
* algorithm, which runs in time O(n log m), where n is the
* length of the range to sort and m is the amount of ascending or
* strictly descending contiguous subsequences usually called 'runs'. The
* algorithm is stable.
*
* @author Rodion Efremov
* @version 2014.11.30
*/
public class Arrays {

/**
* Sorts the entire input array.
*/
public static final >
void sort(final E[] array) {
sort(array, 0, array.length);
}

/**
* Sorts a specific range in the input array.
*/
public static final >
void sort(final E[] array, final int fromIndex, final int toIndex) {
if (toIndex - fromIndex 1) {
final int leftRunLength = deque.dequeue();
final int rightRunLength = deque.dequeue();

merge(source,
target,
offset,
leftRunLength,
rightRunLength);

// Bounce the run we obtained by merging the two runs to the tail.
deque.enqueue(leftRunLength + rightRunLength);

runsLeft -= 2;
offset += leftRunLength + rig

-
RunSizeDeque

-
It is not a deque. Deque, by definition, is double-ended, providing for push and pop on both ends. This class only provides push at tail and pop from front, hence it is a queue. I recommend to either rename it to RunSizeQueue, or implement a complete deque interface.

-
The class implements a generic queue of integers. There is nothing specific to warrant a RunSize prefix.

-
While there is a protection against an overflow (checkCapacityBeforeInsert), there's no protection against underflow - dequeue happily pops a value from an empty queue. Be consistent.

-
Math.power and its allies in such context give me a shiver. I recommend to treat a capacity argument to constructor as a power of 2.

-
RunCounter

-
A comment like // Scan an ascending run is a good indication that a loop wants to be a scan_ascending_run() method. Along the same line, I'd try to unify ascending and descending scans in a same method, because they implement the same algorithm; the only difference being a comparison.

-
reverseRun implements a very important algorithm (aka reverse); it deserves to be public.

-
I'd consider merging it with Arrays class. Both implement array-related algorithms; both has no state.

-
sort

I have a feeling that the overall approach complicates the algorithm with no performance benefits (a simple merge of pairs, then quads, then octets, etc would do as many computations as your calculating runs and merging runs combined). As of now it is just a feeling; I'd try to come back with some math later.

StackExchange Code Review Q#71235, answer score: 3