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 <tt>O(n log m)</tt>, where <tt>n</tt> is the
* length of the range to sort and <tt>m</tt> 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 <E extends Comparable<? super E>>
void sort(final E[] array) {
sort(array, 0, array.length);
}
/**
* Sorts a specific range in the input array.
*/
public static final <E extends Comparable<? super E>>
void sort(final E[] array, final int fromIndex, final int toIndex) {
if (toIndex - fromIndex < 2) {
// Trivially sorted or indices are ass-backwards.
return;
}
final RunSizeDeque deque = RunCounter.buildRunSizeDeque(array,
fromIndex,
toIndex);
final E[] buffer = array.clone();
final int mergePasses = (int) Math.ceil(Math.log(deque.size()) /
Math.log(2));
E[] source;
E[] target;
if ((mergePasses & 1) == 1) {
// Odd amount of passes over the entire range, set the buffer array
// as source so that the sorted shit ends up in the original array.
source = buffer;
target = array;
} else {
source = array;
target = buffer;
}
// The amount of runs in current merge pass that were not processed yet.
int runsLeft = deque.size();
int offset = fromIndex;
// While there are runs to merge, do:
while (deque.size() > 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 + rightRunLength;
switch (runsLeft) {
case 1:
final int singleLength = deque.dequeue();
// In the target array, this 'unmarried' run might be
// in the form of two unmerged runs.
System.arraycopy(source,
offset,
target,
offset,
singleLength);
deque.enqueue(singleLength);
// FALL THROUGH!
case 0:
runsLeft = deque.size();
offset = fromIndex;
final E[] tmp = source;
source = target;
target = tmp;
break;
}
}
}
/**
* This static class method implements the actual merging routine.
* @param <E> the array component type.
* @param source the source array.
* @param target the target array.
* @param offset amount of elements to skip from the beginning of each
* array.
* @param leftRunLength the length of the left run.
* @param rightRunLength the length of the right run.
*/
private static <E extends Comparable<? super E>>
void merge(final E[] source,
final E[] target,
int offset,
int leftRunLength,
int rightRunLength) {
int left = offset;
int right = left + leftRunLength;
final int leftBound = right;
final int rightBound = right + rightRunLength;
while (left < leftBound && right < rightBound) {
target[offset++] = source[right].compareTo(source[left]) < 0 ?
source[right++] :
source[left++];
}
// Either 'left < leftBound' or 'right < rightBound', not both.
if (left < leftBound) {
System.arraycopy(source, left, target, offset, leftBound - left);
} else if (right < rightBound) {
System.arraycopy(source, right, target, offset, rightBound - right);
}
}
/**
* Checks whether all given arrays are of the same length and has identical
* references at every corresponding array components.
*/
public static final <E> boolean arraysEqual(final E[]... arrays) {
if (arrays.length < 2) {
return true;
}
for (int i = 0; i < arrays.length - 1; ++i) {
if (arrays[i].length != arrays[i + 1].length) {
return false;
}
}
for (int idx = 0; idx < arrays[0].length; ++idx) {
for (int i = 0; i < arrays.length - 1; ++i) {
if (arrays[i][idx] != arrays[i + 1][idx]) {
return false;
}
}
}
return true;
}
}
RunCounter.java:
package net.coderodde.util;
/**
* This class provides implementation of a routine for scanning the natural runs
* in the input array. Only monotonically increasing or strictly descending runs
* are recorded. Whenever a descending run is scanned, it is reversed in-situ:
* we constrain the descending runs to strictly descending as not to break the
* relative order of equal elements so that the entire sorting algorithm remains
* stable.
*
* @author Rodion Efremov
* @version 2014.11.30
*/
class RunCounter {
/**
* Scans the runs over the range
* <code>array[fromIndex .. toIndex - 1]</code> and returns a
* {@link RunSizeDeque} containing the sizes of scanned runs in the same
* order as they appear in the input range.
*
* @param <E> the component type.
* @param array the array containing the desired range.
* @param fromIndex the least index of the range to process.
* @param toIndex the index one past the greatest index contained by the
* range.
*
* @return a {@link RunSizeDeque} describing the lengths of the runs in the
* input range.
*/
static <E extends Comparable<? super E>>
RunSizeDeque buildRunSizeDeque(final E[] array,
final int fromIndex,
final int toIndex) {
RunSizeDeque deque = new RunSizeDeque();
int head;
int left = fromIndex;
int right = left + 1;
final int last = toIndex - 1;
while (left < last) {
head = left;
if (array[left++].compareTo(array[right++]) <= 0) {
// Scan an ascending run.
while (left < last
&& array[left].compareTo(array[right]) <= 0) {
++left;
++right;
}
deque.enqueue(left - head + 1);
} else {
// Scan a strictly descending run.
while (left < last
&& array[left].compareTo(array[right]) > 0) {
++left;
++right;
}
deque.enqueue(left - head + 1);
reverseRun(array, head, right);
}
++left;
++right;
}
// A special case: the very last element may be left without buddies
// so make it (the only) 1-element run.
if (left == last) {
deque.enqueue(1);
}
return deque;
}
/**
* Reverses the range <code>array[fromIndex ... toIndex - 1]</code>. Used
* for making descending runs ascending.
*
* @param <E> the component type.
* @param array the array holding the desired range.
* @param fromIndex the least index of the range to reverse.
* @param toIndex the index one past the greatest index of the range.
*/
private static <E> void reverseRun(final E[] array,
final int fromIndex,
final int toIndex) {
for(int l = fromIndex, r = toIndex - 1; l < r; ++l, --r) {
final E tmp = array[l];
array[l] = array[r];
array[r] = tmp;
}
}
}
RunSizeDeque.java:
package net.coderodde.util;
/**
* This is an implementation class for an array-based deque.
*
* @author Rodion Efremov
* @version 2014.11.30
*/
class RunSizeDeque {
private static final int MINIMUM_CAPACITY = 256;
/**
* Stores the actual elements.
*/
private int[] storage;
/**
* Points to the element that will be dequeued next.
*/
private int head;
/**
* Points to the array component to which the next element will be inserted.
*/
private int tail;
/**
* Caches the amount of elements stored.
*/
private int size;
/**
* Used for faster head/tail updates.
*/
private int mask;
RunSizeDeque() {
this(MINIMUM_CAPACITY);
}
RunSizeDeque(int capacity) {
if (capacity < MINIMUM_CAPACITY) {
capacity = MINIMUM_CAPACITY;
}
// Make sure the capacity is a power of two and no less than capacity.
capacity = (int) Math.pow(2,
Math.ceil(Math.log(capacity) / Math.log(2)));
this.mask = capacity - 1;
this.storage = new int[capacity];
}
/**
* Appends a run size to the tail of this deque.
*
* @param runSize the run size to append.
*/
void enqueue(int runSize) {
checkCapacityBeforeInsert();
storage[tail & mask] = runSize;
tail = (tail + 1) & mask;
++size;
}
/**
* Pops from the head of this deque a run size.
*
* @return the run size at the head of this deque.
*/
int dequeue() {
int ret = storage[head];
head = (head + 1) & mask;
--size;
return ret;
}
/**
* Returns the amount of values stored in this deque.
*/
int size() {
return size;
}
private void checkCapacityBeforeInsert() {
if (storage.length == size) {
final int newCapacity = size << 1;
final int[] newStorage = new int[newCapacity];
for (int i = 0; i < size; ++i) {
newStorage[i] = storage[(head + i) & mask];
}
this.storage = newStorage;
this.head = 0;
this.tail = size;
this.mask = newCapacity - 1;
}
}
}
Demo.java:
package net.coderodde.util;
import java.util.Random;
public class Demo {
private static final int N = 1000000;
public static void main(final String... args) {
final long seed = System.currentTimeMillis();
System.out.println("Seed: " + seed);
System.out.println("-- Random data demo --");
final Random rnd = new Random(seed);
Integer[] array1 = getRandomIntegerArray(N, -10000, 10000, rnd);
Integer[] array2 = array1.clone();
System.out.print("My natural merge sort: ");
long ta2 = System.currentTimeMillis();
net.coderodde.util.Arrays.sort(array2);
long tb2 = System.currentTimeMillis();
System.out.println((tb2 - ta2) + " ms.");
System.out.print("java.util.Arrays.sort(): ");
long ta1 = System.currentTimeMillis();
java.util.Arrays.sort(array1);
long tb1 = System.currentTimeMillis();
System.out.println((tb1 - ta1) + " ms.");
System.out.println("Sorted arrays equal: " +
Arrays.arraysEqual(array1, array2));
System.out.println("");
////
System.out.println("-- Presorted data demo --");
array1 = getPresortedIntegerArray(N);
array2 = array1.clone();
System.out.print("My natural merge sort: ");
ta2 = System.currentTimeMillis();
net.coderodde.util.Arrays.sort(array2);
tb2 = System.currentTimeMillis();
System.out.println((tb2 - ta2) + " ms.");
System.out.print("java.util.Arrays.sort(): ");
ta1 = System.currentTimeMillis();
java.util.Arrays.sort(array1);
tb1 = System.currentTimeMillis();
System.out.println((tb1 - ta1) + " ms.");
System.out.println("Sorted arrays equal: " +
Arrays.arraysEqual(array1, array2));
}
private static Integer[] getRandomIntegerArray(final int size,
final int min,
final int max,
final Random rnd) {
final Integer[] array = new Integer[size];
for (int i = 0; i < size; ++i) {
array[i] = rnd.nextInt(max - min + 1) + min;
}
return array;
}
private static Integer[] getPresortedIntegerArray(final int size) {
final Integer[] array = new Integer[size];
for (int i = 0; i < size; ++i) {
array[i] = i % (size / 8);
}
for (int i = 0, j = size - 1; i < j; ++i, --j) {
final Integer tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
return array;
}
private static void printArray(final Integer[] array) {
for (int i = 0; i < array.length; ++i) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
