(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:
AdaptiveMergesort.java
package net.coderodde.util;
import java.util.Arrays;
import java.util.Objects;
public final class AdaptiveMergesort {
private AdaptiveMergesort() {}
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 headInterval1 = run1.first;
Interval headInterval2 = run2.first;
Interval mergedRunHead = null;
Interval mergedRunTail = null;
while (headInterval1 != null && headInterval2 != null) {
T head1 = aux[headInterval1.from];
T head2 = aux[headInterval2.from];
if (head1.compareTo(head2) <= 0) {
T tail1 = aux[headInterval1.to];
if (tail1.compareTo(head2) <= 0) {
if (mergedRunHead == null) {
mergedRunHead = headInterval1;
mergedRunTail = headInterval1;
} else {
mergedRunTail.next = headInterval1;
headInterval1.prev = mergedRunTail;
mergedRunTail = headInterval1;
}
headInterval1 = headInterval1.next;
continue;
}
int index = findUpperBound(aux,
headInterval1.from,
headInterval1.to + 1,
head2);
Interval newInterval = new Interval(headInterval1.from, index - 1);
headInterval1.from = index;
if (mergedRunHead == null) {
mergedRunHead = newInterval;
mergedRunTail = newInterval;
} else {
mergedRunTail.next = newInterval;
newInterval.prev = mergedRunTail;
mergedRunTail = newInterval;
}
} else {
T tail2 = aux[headInterval2.to];
if (tail2.compareTo(head1) < 0) {
if (mergedRunHead == null) {
mergedRunHead = headInterval2;
mergedRunTail = headInterval2;
} else {
mergedRunTail.next = headInterval2;
headInterval2.prev = mergedRunTail;
mergedRunTail = headInterval2;
}
headInterval2 = headInterval2.next;
continue;
}
int index = findLowerBound(aux,
headInterval2.from,
headInterval2.to + 1,
head1);
Interval newInterval = new Interval(headInterval2.from,
index - 1);
headInterval2.from = index;
if (mergedRunHead == null) {
mergedRunHead = newInterval;
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:
if (headInterval1 != null) {
mergedRunTail.next = headInterval1;
headInterval1.prev = mergedRunTail;
mergedRunTail = headInterval1;
} else {
mergedRunTail.next = headInterval2;
headInterval2.prev = mergedRunTail;
mergedRunTail = headInterval2;
}
// Reuse 'run1' in order not to abuse the heap memory:
run1.first = mergedRunHead;
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 final int mask;
private int head;
private int tail;
private int size;
RunQueue(int capacity) {
capacity = ceilCapacityToPowerOfTwo(capacity);
this.mask = capacity - 1;
this.runArray = new Run[capacity];
}
void enqueue(Run run) {
runArray[tail] = run;
tail = (tail + 1) & mask;
++size;
}
void addToLastRun(int runLength) {
runArray[(tail - 1) & mask].first.to += runLength;
}
Run dequeue() {
Run run = runArray[head];
head = (head + 1) & mask;
--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) {
sb.append(separator).append(runArray[(head + i) & mask]);
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 head;
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) {
head = left;
if (array[left++].compareTo(array[right++]) <= 0) {
scanAscendingRun();
} else {
scanDescendingRun();
}
++left;
++right;
}
if (left == last) {
if (array[last - 1].compareTo(array[last]) <= 0) {
queue.addToLastRun(1);
} 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) {
if (array[head - 1].compareTo(array[head]) <= 0) {
queue.addToLastRun(right - head);
} 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);
reverseRun(array, head, left);
if (previousRunWasDesending) {
if (array[head - 1].compareTo(array[head]) <= 0) {
queue.addToLastRun(right - head);
} 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();
AdaptiveMergesort.sort(array2, FROM_INDEX, length - SKIP_RIGHT);
endTime = System.currentTimeMillis();
if (output) {
System.out.println("AdaptiveMergesort.sort in " +
(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;
}
}
}
AdaptiveMergesortTest.java
package net.coderodde.util;
import java.util.Arrays;
import java.util.Random;
import org.junit.Test;
import static org.junit.Assert.*;
public final class AdaptiveMergesortTest {
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);
System.out.println("AdaptiveMergesortTest.testBruteForce(): 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);
AdaptiveMergesort.sort(array2, fromIndex, toIndex);
assertTrue(Arrays.equals(array1, array2));
}
}
@Test(expected = NullPointerException.class)
public void throwsOnNullArray() {
AdaptiveMergesort.sort(null);
}
@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) {
AdaptiveMergesort.sort(array, i, 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) {
AdaptiveMergesort.sort(array, i, i + 1);
}
assertTrue(Arrays.equals(array, new Integer[]{ 8, 3, 6, 1}));
}
@Test
public void testEmptyArray() {
Integer[] array = {};
AdaptiveMergesort.sort(array);
}
@Test
public void testOneElementArray() {
Integer[] array = { 0 };
AdaptiveMergesort.sort(array);
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. AdaptiveMergesort.sort in 7 milliseconds. Algorithms agree: true --- Random array ---- Arrays.sort in 134 milliseconds. AdaptiveMergesort.sort in 78 milliseconds. Algorithms agree: true --- Funny array ----- Arrays.sort in 47 milliseconds. AdaptiveMergesort.sort in 24 milliseconds. Algorithms agree: true --- Runny array ----- Arrays.sort in 71 milliseconds. AdaptiveMergesort.sort in 32 milliseconds. Algorithms agree: true
Critique request
Please tell me anything that comes to mind.
