(See the next iteration.)

This natural merge sort here is from "Sublinear Merging and Natural Mergesort" by Svante Carlsson, Christos Levcopoulos and Ola Petersson. The funky part is that it may merge two sorted runs in sublinear time on some instances. Here it goes:

package net.coderodde.util;

import java.util.Arrays;
import java.util.Objects;

public static <T extends Comparable<? super T>> void sort(T[] array) {
Objects.requireNonNull(array, "The input array is null.");
sort(array, 0, array.length);
}

public static <T extends Comparable<? super T>> void sort(T[] array,
int fromIndex,
int toIndex) {
Objects.requireNonNull(array, "The input array is null.");
checkIndices(array.length, fromIndex, toIndex);

int rangeLength = toIndex - fromIndex;

if (rangeLength < 2) {
return; // Trivially sorted.
}

T[] aux = Arrays.copyOfRange(array, fromIndex, toIndex);
RunQueue queue = new RunLengthQueueBuilder<>(aux).run();
int runsLeft = queue.size();

while (queue.size() > 1) {
switch (runsLeft) {
case 1:
// Bounce the lonely leftover run back to the tail of the
// queue:
queue.enqueue(queue.dequeue());
// Fall through!

case 0:
runsLeft = queue.size();
continue;
}

Run run1 = queue.dequeue();
Run run2 = queue.dequeue();
queue.enqueue(merge(aux, run1, run2));
}

int arrayIndex = fromIndex;

for (Interval interval = queue.dequeue().first;
interval != null;
interval = interval.next) {
for (int i = interval.from; i <= interval.to; ++i) {
array[arrayIndex++] = aux[i];
}
}
}

private static <T extends Comparable<? super T>> Run merge(T[] aux,
Run run1,
Run run2) {
Interval mergedRunTail = null;

} else {
}

continue;
}

int index = findUpperBound(aux,

Interval newInterval = new Interval(headInterval1.from, index - 1);

mergedRunTail = newInterval;
} else {
mergedRunTail.next = newInterval;
newInterval.prev = mergedRunTail;
mergedRunTail = newInterval;
}
} else {

} else {
}

continue;
}

int index = findLowerBound(aux,

index - 1);

mergedRunTail = newInterval;
} else {
mergedRunTail.next = newInterval;
newInterval.prev = mergedRunTail;
mergedRunTail = newInterval;
}
}
}

// Append the leftover intervals of a currently non-empty run to the
// tail of the merged run:
} else {
}

// Reuse 'run1' in order not to abuse the heap memory:
run1.last = mergedRunTail;
return run1;
}

private static void checkIndices(int arrayLength,
int fromIndex,
int toIndex) {
if (fromIndex > toIndex) {
throw new IllegalArgumentException(
"fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
}

if (fromIndex < 0) {
throw new ArrayIndexOutOfBoundsException(
"fromIndex = " + fromIndex);
}

if (toIndex > arrayLength) {
throw new ArrayIndexOutOfBoundsException(
"toIndex = " + toIndex);
}
}

private static final class Interval {
int from;
int to;
Interval prev;
Interval next;

Interval(int from, int to) {
this.from = from;
this.to = to;
}

@Override
public String toString() {
return "(" + from + ", " + to + ")";
}
}

private static final class Run {
Interval first;
Interval last;

Run(int from, int to) {
first = new Interval(from, to);
last = first;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
String separator = "";

for (Interval interval = first;
interval != null;
interval = interval.next) {
sb.append(separator).append(interval);
separator = ", ";
}

return sb.append("]").toString();
}
}

private static final class RunQueue {

private final Run[] runArray;
private int tail;
private int size;

RunQueue(int capacity) {
capacity = ceilCapacityToPowerOfTwo(capacity);
this.runArray = new Run[capacity];
}

void enqueue(Run run) {
runArray[tail] = run;
tail = (tail + 1) & mask;
++size;
}

runArray[(tail - 1) & mask].first.to += runLength;
}

Run dequeue() {
--size;
return run;
}

int size() {
return size;
}

private static int ceilCapacityToPowerOfTwo(int capacity) {
int ret = Integer.highestOneBit(capacity);
return ret != capacity ? ret << 1 : ret;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
String separator = "";

for (int i = 0; i < size; ++i) {
separator = ", ";
}

return sb.append("]").toString();
}
}

private static final class
RunLengthQueueBuilder<T extends Comparable<? super T>> {

private final RunQueue queue;
private final T[] array;
private int left;
private int right;
private final int last;
private boolean previousRunWasDesending;

RunLengthQueueBuilder(T[] array) {
this.queue = new RunQueue((array.length >>> 1) + 1);
this.array = array;
this.left  = 0;
this.right = 1;
this.last  = array.length - 1;
}

RunQueue run() {
while (left < last) {

if (array[left++].compareTo(array[right++]) <= 0) {
scanAscendingRun();
} else {
scanDescendingRun();
}

++left;
++right;
}

if (left == last) {
if (array[last - 1].compareTo(array[last]) <= 0) {
} else {
queue.enqueue(new Run(left, left));
}
}

return queue;
}

void scanAscendingRun() {
while (left < last && array[left].compareTo(array[right]) <= 0) {
++left;
++right;
}

Run run = new Run(head, left);

if (previousRunWasDesending) {
} else {
queue.enqueue(run);
}
} else {
queue.enqueue(run);
}

previousRunWasDesending = false;
}

void scanDescendingRun() {
while (left < last && array[left].compareTo(array[right]) > 0) {
++left;
++right;
}

Run run = new Run(head, left);

if (previousRunWasDesending) {
} else {
queue.enqueue(run);
}
} else {
queue.enqueue(run);
}

previousRunWasDesending = true;
}

private void reverseRun(T[] array, int i, int j) {
for (; i < j; ++i, --j) {
T tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}

private static <T extends Comparable<? super T>>
int lowerBound(T[] array, int fromIndex, int toIndex, T value) {
int count = toIndex - fromIndex;
int it;

while (count > 0) {
it = fromIndex;
int step = count >>> 1;
it += step;

if (array[it].compareTo(value) < 0) {
fromIndex = ++it;
count -= step + 1;
} else {
count = step;
}
}

return fromIndex;
}

private static <T extends Comparable<? super T>>
int upperBound(T[] array, int fromIndex, int toIndex, T value) {
int count = toIndex - fromIndex;
int it;

while (count > 0) {
it = fromIndex;
int step = count >>> 1;
it += step;

if (array[it].compareTo(value) <= 0) {
fromIndex = ++it;
count -= step + 1;
} else {
count = step;
}
}

return fromIndex;
}

private static <T extends Comparable<? super T>>
int findLowerBound(T[] array, int fromIndex, int toIndex, T value) {
int bound = 1;
int rangeLength = toIndex - fromIndex;

while (bound < rangeLength &&
array[bound + fromIndex].compareTo(value) < 0) {
bound <<= 1;
}

return lowerBound(array,
fromIndex + (bound >>> 1),
Math.min(toIndex, fromIndex + bound),
value);
}

private static <T extends Comparable<? super T>>
int findUpperBound(T[] array, int fromIndex, int toIndex, T value) {
int bound = 1;
int rangeLength = toIndex - fromIndex;

while (bound < rangeLength
&& array[bound + fromIndex].compareTo(value) < 0) {
bound <<= 1;
}

return upperBound(array,
fromIndex + (bound >>> 1),
Math.min(toIndex, fromIndex + bound),
value);
}
}


Demo.java

package net.coderodde.util;

import java.util.Arrays;
import java.util.Random;

public final class Demo {

private static final int FROM_INDEX = 7;
private static final int SKIP_RIGHT = 9;
private static final int ARRAY_LENGTH = 50_000;
private static final int BLOCKS = 1000;
private static final int MIN_ELEMENT = -10_000;
private static final int MAX_ELEMENT = 10_000;
private static final int MAX_RUN_LENGTH = 100;
private static final int RUNS = 1000;

public static void main(String[] args) {
long seed = System.currentTimeMillis();
Random random = new Random(seed);
System.out.println("Seed = " + seed);

warmup(random);
benchmark(random);
}

private static void warmup(Random random) {
System.out.println("Warming up...");

Integer[] array = getBlockedArray(ARRAY_LENGTH, BLOCKS, random);
warmup(array);

array = getRandomArray(ARRAY_LENGTH, random);
warmup(array);

array = getFunnyArray(ARRAY_LENGTH, random);
warmup(array);

array = getRunnyArray(ARRAY_LENGTH, RUNS, random);
warmup(array);

System.out.println("Warming up done!\n\n");
}

private static void benchmark(Random random) {
Integer[] array = getBlockedArray(ARRAY_LENGTH, BLOCKS, random);
System.out.println("--- Blocked array ---");
benchmark(array);

array = getRandomArray(ARRAY_LENGTH, random);
System.out.println("--- Random array ----");
benchmark(array);

array = getFunnyArray(ARRAY_LENGTH, random);
System.out.println("--- Funny array -----");
benchmark(array);

array = getRunnyArray(ARRAY_LENGTH, RUNS, random);
System.out.println("--- Runny array -----");
benchmark(array);
}

private static void warmup(Integer[] array1) {
perform(false, array1);
}

private static void benchmark(Integer[] array1) {
perform(true, array1);
}

private static void perform(boolean output,
Integer[] array1) {
Integer[] array2 = array1.clone();
int length = array1.length;

long startTime = System.currentTimeMillis();
Arrays.sort(array1, FROM_INDEX, length - SKIP_RIGHT);
long endTime = System.currentTimeMillis();

if (output) {
System.out.println("Arrays.sort in " + (endTime - startTime) +
" milliseconds.");
}

startTime = System.currentTimeMillis();
endTime = System.currentTimeMillis();

if (output) {
(endTime - startTime) +
" milliseconds.");

System.out.println("Algorithms agree: " +
Arrays.equals(array1, array2));
}
}

private static final Integer[] getBlockedArray(int length,
int blocks,
Random random) {
Integer[] array = getAscendingArray(length);
blockify(array, blocks, random);
return array;
}

private static final Integer[] getRandomArray(int length, Random random) {
Integer[] array = new Integer[length];

for (int i = 0; i < length; ++i) {
array[i] = random.nextInt(MAX_ELEMENT - MIN_ELEMENT + 1) + MIN_ELEMENT;
}

return array;
}

private static final Integer[] getFunnyArray(int length, Random random) {
Integer[] array = new Integer[length];

int index = 0;

while (index < array.length) {
int remaining = array.length - index;
int next = random.nextInt(MAX_RUN_LENGTH);
int actual = Math.min(remaining, next);
boolean direction = random.nextBoolean();

Integer first =
MIN_ELEMENT +
random.nextInt(MAX_ELEMENT - MIN_ELEMENT + 1);

array[index++] = first;
int step = 1 + random.nextInt(5);

if (direction) {
for (int i = 1; i < actual; ++i) {
array[index++] = first + i * step;
}
} else {
for (int i = 1; i < actual; ++i) {
array[index++] = first - i * step;
}
}
}

return array;
}

private static final Integer[] getRunnyArray(int length,
int runLength,
Random random) {
Integer[] array = getRandomArray(length, random);

int index = 0;

while (index < length) {
int remaining = length - index;
int requested = random.nextInt(runLength);
int actual = Math.min(remaining, requested);

Arrays.sort(array, index, index + actual);
index += actual;
}

return array;
}

private static final Integer[] getAscendingArray(int length) {
Integer[] array = new Integer[length];

for (int i = 0; i < length; ++i) {
array[i] = i;
}

return array;
}

private static void blockify(Integer[] array,
int numberOfBlocks,
Random random) {
int blockSize = array.length / numberOfBlocks;
Integer[][] blocks = new Integer[numberOfBlocks][];

for (int i = 0; i < numberOfBlocks - 1; ++i) {
blocks[i] = new Integer[blockSize];
}

blocks[numberOfBlocks - 1] =
new Integer[blockSize + array.length % blockSize];

int index = 0;

for (Integer[] block : blocks) {
for (int i = 0; i < block.length; ++i) {
block[i] = array[index++];
}
}

shuffle(blocks, random);

index = 0;

for (Integer[] block : blocks) {
for (int i = 0; i < block.length; ++i) {
array[index++] = block[i];
}
}
}

private static void shuffle(Integer[][] blocks, Random random) {
for (int i = 0; i < blocks.length; ++i) {
int index1 = random.nextInt(blocks.length);
int index2 = random.nextInt(blocks.length);
Integer[] block = blocks[index1];
blocks[index1] = blocks[index2];
blocks[index2] = block;
}
}
}


package net.coderodde.util;

import java.util.Arrays;
import java.util.Random;
import org.junit.Test;
import static org.junit.Assert.*;

private static final int BRUTE_FORCE_ITERATIONS = 1000;
private static final int MAXIMUM_ARRAY_LENGTH = 100;
private static final int MIN_ELEMENT = -50;
private static final int MAX_ELEMENT = 50;
private static final int MINIMUM_ARRAY_LENGTH = 3;

@Test
public void testBruteForce() {
long seed = System.currentTimeMillis();
Random random = new Random(seed);

seed);

for (int i = 0; i < BRUTE_FORCE_ITERATIONS; ++i) {
int arrayLength = random.nextInt(MAXIMUM_ARRAY_LENGTH + 1);
arrayLength = Math.max(arrayLength, MINIMUM_ARRAY_LENGTH);

int fromIndex = random.nextInt(arrayLength / 2);
int toIndex = arrayLength - random.nextInt(arrayLength / 2);
Integer[] array1 = getRandomArray(arrayLength, random);
Integer[] array2 = array1.clone();

Arrays.sort(array1, fromIndex, toIndex);

assertTrue(Arrays.equals(array1, array2));
}
}

@Test(expected = NullPointerException.class)
public void throwsOnNullArray() {
}

@Test(expected = IllegalArgumentException.class)
public void testThrowsOnReversedFromIndexToIndex() {
AdaptiveMergesort.sort(new Integer[]{ 1, 2, 3 }, 1, 0);
}

@Test(expected = IndexOutOfBoundsException.class)
public void testThrowsOnNegativeFromIndex() {
AdaptiveMergesort.sort(new Integer[]{ 1, 2, 3}, -1, 2);
}

@Test(expected = IndexOutOfBoundsException.class)
public void testThrowsOnTooLargeToIndex() {
AdaptiveMergesort.sort(new Integer[]{ 1, 2, 3 }, 1, 4);
}

@Test
public void testEmptyArrayWithIndices() {
Integer[] array = { 4, 1, 8, 2 };

for (int i = 0; i < array.length; ++i) {
}

assertTrue(Arrays.equals(array, new Integer[]{ 4, 1, 8, 2}));
}

@Test
public void testOneElementArrayWithIndices() {
Integer[] array = { 8, 3, 6, 1 };

for (int i = 0; i < array.length - 1; ++i) {
}

assertTrue(Arrays.equals(array, new Integer[]{ 8, 3, 6, 1}));
}

@Test
public void testEmptyArray() {
Integer[] array = {};
}

@Test
public void testOneElementArray() {
Integer[] array = { 0 };
assertTrue(Arrays.equals(array, new Integer[]{ 0 }));
}

private static Integer[] getRandomArray(int length, Random random) {
Integer[] array = new Integer[length];

for (int i = 0; i < length; ++i) {
array[i] = MIN_ELEMENT +
random.nextInt(MAX_ELEMENT - MIN_ELEMENT + 1);
}

return array;
}
}


# Sample output

It is slow on larger arrays, yet on mid-sized arrays it performs well.

Seed = 1508092238415
Warming up...
Warming up done!

--- Blocked array ---
Arrays.sort in 12 milliseconds.
Algorithms agree: true
--- Random array ----
Arrays.sort in 134 milliseconds.
Algorithms agree: true
--- Funny array -----
Arrays.sort in 47 milliseconds.
Algorithms agree: true
--- Runny array -----
Arrays.sort in 71 milliseconds.
Algorithms agree: true


# Critique request

Please tell me anything that comes to mind.

        int runsLeft = queue.size();

while (queue.size() > 1) {
switch (runsLeft) {
case 1:
// Bounce the lonely leftover run back to the tail of the
// queue:
queue.enqueue(queue.dequeue());
// Fall through!

case 0:
runsLeft = queue.size();
continue;
}

Run run1 = queue.dequeue();
Run run2 = queue.dequeue();
queue.enqueue(merge(aux, run1, run2));
}


My first instinct was that this is buggy: I'm still not sure whether it's buggy or merely over-complicated.

Let R be the initial value of runsLeft. If we enter the while loop then it's because R > 1, so neither of the cases in the switch (which IMO should have an explicit default for clarity) are ever executed, and runsLeft will never change. Therefore the entire switch block could be removed without affecting the behaviour of the code.

Should it be switch (runsLeft--)?

        if (headInterval1 != null) {
} else {
}


KISS:

        mergedRunTail.next = headInterval1 != null ? headInterval1

• You are right, it should have been runsLeft -= 2. It did not affect the correctness of the sort, but it was unstable. Oct 16, 2017 at 9:18