See the previous iteration: Natural merge sort in Java
See the next iteration: Natural merge sort in Java - follow-up 2
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' in the
* input range. The algorithm is stable.
*
* @author Rodion Efremov
* @version 2014.12.01
*/
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 UnsafeIntQueue queue = buildRunSizeQueue(array,
fromIndex,
toIndex);
final E[] buffer = array.clone();
final int mergePasses = getPassAmount(queue.size());
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 = queue.size();
int offset = fromIndex;
// While there are runs to merge, do:
while (queue.size() > 1) {
final int leftRunLength = queue.dequeue();
final int rightRunLength = queue.dequeue();
merge(source,
target,
offset,
leftRunLength,
rightRunLength);
// Bounce the run we obtained by merging the two runs to the tail.
queue.enqueue(leftRunLength + rightRunLength);
runsLeft -= 2;
offset += leftRunLength + rightRunLength;
switch (runsLeft) {
case 1:
final int singleLength = queue.dequeue();
// In the target array, this 'unmarried' run might be
// in the form of two unmerged runs.
System.arraycopy(source,
offset,
target,
offset,
singleLength);
queue.enqueue(singleLength);
// FALL THROUGH!
case 0:
runsLeft = queue.size();
offset = fromIndex;
final E[] tmp = source;
source = target;
target = tmp;
break;
}
}
}
/**
* 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.
*/
public 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;
}
}
/**
* 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;
}
/**
* 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);
}
}
/**
* This class method returns the amount of merge passes over the input range
* needed to sort <code>runAmount</code> runs.
*/
private static int getPassAmount(int runAmount) {
int setBitCount = 0;
int mostSignificantBitIndex = -1;
int mask = 0x40000000;
loop:
for (int i = 30; i >= 0; --i, mask >>= 1) {
if ((runAmount & mask) != 0) {
++setBitCount;
switch (setBitCount) {
case 1:
mostSignificantBitIndex = i;
break;
case 2:
break loop;
}
}
}
if (setBitCount > 1) {
// Once here, 'runAmount' is not a power of two; make it one.
runAmount = (1 << (mostSignificantBitIndex + 1));
}
int ret = 0;
while ((runAmount & 1) == 0) {
++ret;
runAmount >>= 1;
}
return ret;
}
/**
* Scans the runs over the range
* <code>array[fromIndex .. toIndex - 1]</code> and returns a
* {@link UnsafeIntQueue} 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 UnsafeIntQueue} describing the lengths of the runs in
* the input range.
*/
static <E extends Comparable<? super E>>
UnsafeIntQueue buildRunSizeQueue(final E[] array,
final int fromIndex,
final int toIndex) {
final UnsafeIntQueue queue =
new UnsafeIntQueue(((toIndex - fromIndex) >>> 1) + 1);
int head;
int left = fromIndex;
int right = left + 1;
final int last = toIndex - 1;
while (left < last) {
head = left;
// Decide the direction of the next run.
if (array[left++].compareTo(array[right++]) <= 0) {
// Scan an ascending run.
while (left < last
&& array[left].compareTo(array[right]) <= 0) {
++left;
++right;
}
queue.enqueue(left - head + 1);
} else {
// Scan a strictly descending run.
while (left < last
&& array[left].compareTo(array[right]) > 0) {
++left;
++right;
}
queue.enqueue(left - head + 1);
// We reverse a strictly descending run as to minimize the
// the amount of runs scanned in total. Strictness is required.
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) {
queue.enqueue(1);
}
return queue;
}
/**
* This is the implementation class for an array-based queue of integers. It
* sacrifices under- and overflow checks as to squeeze a little bit more of
* efficiency and thus is an ad-hoc data structure hidden from the client
* programmers.
*
* @author Rodion Efremov
* @version 2014.12.01
*/
private static class UnsafeIntQueue {
/**
* The minimum capacity of this queue.
*/
private static final int MINIMUM_CAPACITY = 256;
/**
* Stores the actual elements.
*/
private final 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 final int mask;
/**
* Creates an empty integer queue with capacity of the least power of
* two no less than original capacity value.
*/
UnsafeIntQueue(int capacity) {
capacity = fixCapacity(capacity);
this.mask = capacity - 1;
this.storage = new int[capacity];
}
/**
* Appends a run size to the tail of this queue.
*
* @param runSize the run size to append.
*/
void enqueue(int runSize) {
storage[tail & mask] = runSize;
tail = (tail + 1) & mask;
++size;
}
/**
* Pops from the head of this queue a run size.
*
* @return the run size at the head of this queue.
*/
int dequeue() {
int ret = storage[head];
head = (head + 1) & mask;
--size;
return ret;
}
/**
* Returns the amount of values stored in this queue.
*/
int size() {
return size;
}
/**
* This routine is responsible for computing an integer that is a power
* of two no less than <code>capacity</code>.
*/
private static int fixCapacity(int capacity) {
if (capacity < MINIMUM_CAPACITY) {
capacity = MINIMUM_CAPACITY;
}
int mask = 0x40000000;
int totalSetBits = 0;
int mostSignificantBitIndex = -1;
loop:
for (int i = 30; i >= 0; mask >>= 1, --i) {
if ((capacity & mask) != 0) {
++totalSetBits;
switch (totalSetBits) {
case 1:
mostSignificantBitIndex = i;
break;
case 2:
break loop;
}
}
}
if (totalSetBits > 1) {
// Make capacity a power of two that is no less than
// input capacity
capacity = (1 << (mostSignificantBitIndex + 1));
}
// Here, capacity is a power of two.
return capacity;
}
}
}
Demo.java
package net.coderodde.util;
import java.util.Random;
public class Demo {
private static final int N = 2000000;
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 ta1 = System.currentTimeMillis();
net.coderodde.util.Arrays.sort(array2);
long tb1 = System.currentTimeMillis();
System.out.println((tb1 - ta1) + " ms.");
System.out.print("java.util.Arrays.sort(): ");
long ta2 = System.currentTimeMillis();
java.util.Arrays.sort(array1);
long tb2 = System.currentTimeMillis();
System.out.println((tb2 - ta2) + " 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: ");
ta1 = System.currentTimeMillis();
net.coderodde.util.Arrays.sort(array2);
tb1 = System.currentTimeMillis();
System.out.println((tb1 - ta1) + " ms.");
System.out.print("java.util.Arrays.sort(): ");
ta2 = System.currentTimeMillis();
java.util.Arrays.sort(array1);
tb2 = System.currentTimeMillis();
System.out.println((tb2 - ta2) + " 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;
}
}
RunSizeDeque
- Renamed to UnsafeIntQueue as to reflect the fact that it is a queue of primitive integers, and that the structure does not check for under-/overflow for efficiency.
- Hidden from client programmer as a static private inner class of net.coderodde.util.Arrays.
- Avoids using stuff from java.lang.Math to compute a capacity that is a power of 2.
- The user of UnsafeIntQueue, i.e. the sort method, will do everything needed to avoid under-/overflow.
RunCounter
- Moved to net.coderodde.util.Arrays in the form of a private static method.
- I disagree about the need to encapsulate run scanning logic into a subroutine, and that's why:
- It's only a loop with a body containing two simple updates.
- As it will be called in the worst case O(n) times, and calls in general are expensive, it will introduce an efficiency penalty which I want to avoid.
- And, no. The code will not be any more readable.
- reverseRun renamed to reverse and made public as it implements an "important algorithm."
- sort
- Eliminates the need for java.lang.Math-stuff.
- What comes to efficiency, just run the demo and you'll see.
- If the input array has length, say, n = 2k, and is of form $$\langle 1, 2, \dots, k, k, k - 1, \dots, 2, 1 \rangle,$$ natural merge sort will do one pass over the array just to find out that it consists of two runs, the second of which is reversed, reverse it, and do a single merge over the array to merge the two. That's it! 2 and a half passes over the range instead of $$\log 2k = \log k + 1.$$
