I fixed the stability issue in the previous iteration. Also, I incorporated nice points by Peter Tailor

I fixed the stability issue in the previous iteration. Also, I incorporated nice points by Peter Taylor

Benchmark

The algorithm is slow on large array (over one hundred thousand elements), but performs better than Arrays.sort (which is TimSort) on middle-sized arrays:

Seed = 1508165374965
Warming up...
Warming up done!
--- Blocked array ---
Arrays.sort in 4 milliseconds.
AdaptiveMergesort.sort in 4 milliseconds.
Algorithms agree: true

--- Random array ----
Arrays.sort in 89 milliseconds.
AdaptiveMergesort.sort in 91 milliseconds.
Algorithms agree: true

--- Funny array -----
Arrays.sort in 42 milliseconds.
AdaptiveMergesort.sort in 19 milliseconds.
Algorithms agree: true

--- Runny array -----
Arrays.sort in 78 milliseconds.
AdaptiveMergesort.sort in 33 milliseconds.
Algorithms agree: true

--- Zig zag array ---
Arrays.sort in 3 milliseconds.
AdaptiveMergesort.sort in 4 milliseconds.
Algorithms agree: true

Seed = 1508165374965 Warming up... Warming up done!

--- Blocked array --- Arrays.sort in 4 milliseconds. AdaptiveMergesort.sort in 4 milliseconds. Algorithms agree: true

--- Random array ---- Arrays.sort in 89 milliseconds. AdaptiveMergesort.sort in 91 milliseconds. Algorithms agree: true

--- Funny array ----- Arrays.sort in 42 milliseconds. AdaptiveMergesort.sort in 19 milliseconds. Algorithms agree: true

--- Runny array ----- Arrays.sort in 78 milliseconds. AdaptiveMergesort.sort in 33 milliseconds. Algorithms agree: true

--- Zig zag array --- Arrays.sort in 3 milliseconds. AdaptiveMergesort.sort in 4 milliseconds. Algorithms agree: true

Seed = 1508165374965
Warming up...
Warming up done!
--- Blocked array ---
Arrays.sort in 4 milliseconds.
AdaptiveMergesort.sort in 4 milliseconds.
Algorithms agree: true

--- Random array ----
Arrays.sort in 89 milliseconds.
AdaptiveMergesort.sort in 91 milliseconds.
Algorithms agree: true

--- Funny array -----
Arrays.sort in 42 milliseconds.
AdaptiveMergesort.sort in 19 milliseconds.
Algorithms agree: true

--- Runny array -----
Arrays.sort in 78 milliseconds.
AdaptiveMergesort.sort in 33 milliseconds.
Algorithms agree: true

--- Zig zag array ---
Arrays.sort in 3 milliseconds.
AdaptiveMergesort.sort in 4 milliseconds.
Algorithms agree: true