See the the previous iteration.
Now I refactored the code a bit so that I do not need to pass like 6 parameters to helper methods. Also, I did a small tweak that allows the sort to arrive to the state where the amount of runs is a power of two, which solves the orphan issue: suppose your data has \$1048577 = 2^{20} + 1\$ runs. Now normally you would sort the first \$2^{20}\$ runs, after which you would have to perform another large merge over the entire range in order to merge the last orphan run.
Also, I ignored the generics and pass to my sort any object that implements Comparable. Now, what do you think?
NaturalMergesort.java:
package net.coderodde.util.sorting;
import java.util.Arrays;
/**
* This class implements natural merge sort for {@code Comparable} objects.
*
* @author Rodion "rodde" Efremov
* @version 1.61 (Oct 1, 2015)
*/
public final class NaturalMergesort {
private Object[] source;
private Object[] target;
private int sourceOffset;
private int targetOffset;
private UnsafeIntQueue queue;
private NaturalMergesort(Object[] array, int fromIndex, int toIndex) {
if (toIndex - fromIndex < 2) {
// Nothing to sort.
return;
}
this.queue = buildRunSizeQueue(array, fromIndex, toIndex);
Object[] buffer = Arrays.copyOfRange(array, fromIndex, toIndex);
int mergePasses = getPassAmount(queue.size());
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;
sourceOffset = 0;
targetOffset = fromIndex;
} else {
// Arrange the stuff such that after the last merge pass all shit is
// in the argument array.
source = array;
target = buffer;
sourceOffset = fromIndex;
targetOffset = 0;
}
sort();
}
private void sort() {
// The amount of runs in current merge pass that were not processed yet.
int runsLeft = queue.size();
// The amount of elements processed from beginnig of the ranges.
int offset = 0;
// While there are runs to merge, do:
while (queue.size() > 1) {
if (runsLeft == 3) {
// We handle this special case in order to get fast to the state
// where the amount of remaining runs is a power of two. We do
// this for the following reason: Suppose you have 1048577 =
// 1048576 + 1 = 2^(20) + 1 elements in the requested range.
// Now the algorithm would sort the first 2^(20) element AND
// will have to do one more merge pass just for putting the last
// orphan element to its correct position.
int leftRunLength = queue.dequeue();
int middleRunLength = queue.dequeue();
int rightRunLength = queue.dequeue();
merge(offset,
leftRunLength,
middleRunLength,
rightRunLength);
queue.enqueue(leftRunLength +
middleRunLength + rightRunLength);
int itmp = sourceOffset;
sourceOffset = targetOffset;
targetOffset = itmp;
Object[] tmp = source;
source = target;
target = tmp;
runsLeft = queue.size();
offset = 0;
continue;
}
int leftRunLength = queue.dequeue();
int rightRunLength = queue.dequeue();
merge(offset,
leftRunLength,
rightRunLength);
// Bounce the run we obtained by merging the two runs to the tail.
queue.enqueue(leftRunLength + rightRunLength);
offset += leftRunLength + rightRunLength;
runsLeft -= 2;
if (runsLeft == 0) {
// Swap array offsets.
int itmp = sourceOffset;
sourceOffset = targetOffset;
targetOffset = itmp;
// Swap array roles.
Object[] tmp = source;
source = target;
target = tmp;
// Go to the beginning of the array.
runsLeft = queue.size();
offset = 0;
}
}
}
/**
* Sorts the entire input array.
*
* @param array the array to sort.
*/
public static void sort(Object[] array) {
sort(array, 0, array.length);
}
/**
* Sorts a specific range in the input array.
*
* @param array the array holding the target range.
* @param fromIndex the starting, inclusive index of the range to sort.
* @param toIndex the ending, exclusive index of the range to sort.
*/
public static void sort(Object[] array, int fromIndex, int toIndex) {
new NaturalMergesort(array, fromIndex, toIndex).sort();
}
/**
* Reverses the range <code>array[fromIndex ... toIndex - 1]</code>. Used
* for making descending runs ascending.
*
* @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 void reverseRun(Object[] array,
int fromIndex,
int toIndex) {
for(int l = fromIndex, r = toIndex - 1; l < r; ++l, --r) {
Object tmp = array[l];
array[l] = array[r];
array[r] = tmp;
}
}
/**
* This method implements a 3-way merge operation.
*
* @param offset the amount of elements to skip from the beginning
* of the ranges.
* @param leftRunLength the length of the left run.
* @param middleRunLength the length of the middle run.
* @param rightRunLength the length of the right run.
*/
private void merge(int offset,
int leftRunLength,
int middleRunLength,
int rightRunLength) {
int left = sourceOffset + offset;
int middle = left + leftRunLength;
int right = middle + middleRunLength;
int leftBound = middle;
int middleBound = right;
int rightBound = right + rightRunLength;
int placementOffset = targetOffset + offset;
while (left < leftBound && middle < middleBound && right < rightBound) {
Comparable cLeft = (Comparable) source[left];
Comparable cMiddle = (Comparable) source[middle];
Comparable cRight = (Comparable) source[right];
if (cRight.compareTo(cMiddle) < 0) {
// Here, cRight < cMiddle
if (cRight.compareTo(cLeft) < 0) {
target[placementOffset++] = cRight;
++right;
} else {
target[placementOffset++] = cLeft;
++left;
}
} else {
// Here, cMiddle <= cRight.
if (cLeft.compareTo(cMiddle) <= 0) {
target[placementOffset++] = cLeft;
++left;
} else {
target[placementOffset++] = cMiddle;
++middle;
}
}
}
while (left < leftBound && middle < middleBound) {
Comparable cLeft = (Comparable) source[left];
Comparable cMiddle = (Comparable) source[middle];
target[placementOffset++] = cMiddle.compareTo(cLeft) < 0 ?
source[middle++] :
source[left++] ;
}
while (left < leftBound && right < rightBound) {
Comparable cLeft = (Comparable) source[left];
Comparable cRight = (Comparable) source[right];
target[placementOffset++] = cRight.compareTo(cLeft) < 0 ?
source[right++] :
source[left++];
}
while (middle < middleBound && right < rightBound) {
Comparable cMiddle = (Comparable) source[middle];
Comparable cRight = (Comparable) source[right];
target[placementOffset++] = cMiddle.compareTo(cRight) < 0 ?
source[middle++] :
source[right++];
}
System.arraycopy(source,
left,
target,
placementOffset,
leftBound - left);
System.arraycopy(source,
middle,
target,
placementOffset,
middleBound - middle);
System.arraycopy(source,
right,
target,
placementOffset,
rightBound - right);
}
/**
* This method implements the merging routine.
*
* @param offset the 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 void merge(int offset,
int leftRunLength,
int rightRunLength) {
int left = sourceOffset + offset;
int right = left + leftRunLength;
int leftBound = right;
int rightBound = right + rightRunLength;
int placementOffset = targetOffset + offset;
while (left < leftBound && right < rightBound) {
target[placementOffset++] =
((Comparable) source[right]).compareTo(source[left]) < 0 ?
source[right++] :
source[left++];
}
System.arraycopy(source,
left,
target,
placementOffset,
leftBound - left);
System.arraycopy(source,
right,
target,
placementOffset,
rightBound - right);
}
/**
* This class method returns the amount of merge passes over the input range
* needed to sort {@code runAmount} runs.
*/
private static int getPassAmount(int runAmount) {
return 32 - Integer.numberOfLeadingZeros(runAmount / 2);
}
/**
* Scans the runs over the range {@code array[fromIndex .. toIndex - 1]} and
* returns a {@link UnsafeIntQueue} containing the sizes of scanned runs in
* the same order as they appear in the input range.
*
* @param array the array containing the desired range.
* @param fromIndex the starting, inclusive index of the range to scan.
* @param toIndex the ending, exclusive index of the range to scan.
*
* @return a {@code UnsafeIntQueue} describing the lengths of the runs in
* the input range.
*/
static UnsafeIntQueue buildRunSizeQueue(Object[] array,
int fromIndex,
int toIndex) {
UnsafeIntQueue queue =
new UnsafeIntQueue(((toIndex - fromIndex) >>> 1) + 1);
int head;
int left = fromIndex;
int right = left + 1;
int last = toIndex - 1;
while (left < last) {
head = left;
// Decide the direction of the next run.
if (((Comparable) array[left++]).compareTo(array[right++]) <= 0) {
// Scan an ascending run.
while (left < last
&& ((Comparable) array[left])
.compareTo(array[right]) <= 0) {
++left;
++right;
}
queue.enqueue(left - head + 1);
} else {
// Scan a strictly descending run.
while (left < last
&& ((Comparable) 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 final 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 an integer to the tail of this queue.
*
* @param num the integer to append.
*/
void enqueue(int num) {
storage[tail & mask] = num;
tail = (tail + 1) & mask;
++size;
}
/**
* Pops from the head of this queue an integer.
*
* @return the integer 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}.
*/
private static int fixCapacity(int capacity) {
capacity = Math.max(capacity, MINIMUM_CAPACITY);
int ret = 1;
while (ret < capacity) {
ret <<= 1;
}
return ret;
}
}
}
Demo.java:
import java.util.Arrays;
import java.util.Random;
import net.coderodde.util.sorting.NaturalMergesort;
public class Demo {
private static final int ARRAY_LENGTH = 2000000;
private static final int FROM_INDEX = 5;
private static final int TO_INDEX = ARRAY_LENGTH - 6;
static int getPasses(int runs) {
return 32 - Integer.numberOfLeadingZeros(runs / 2);
}
public static void main(final String... args) {
long seed = System.currentTimeMillis();
System.out.println("Seed: " + seed);
System.out.println();
System.out.println("-- Random data demo --");
Random rnd = new Random(seed);
Integer[] array1 = getRandomIntegerArray(ARRAY_LENGTH,
-10000,
10000,
rnd);
Integer[] array2 = array1.clone();
System.out.print("My natural merge sort: ");
long ta1 = System.currentTimeMillis();
NaturalMergesort.sort(array2, FROM_INDEX, TO_INDEX);
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, FROM_INDEX, TO_INDEX);
long tb2 = System.currentTimeMillis();
System.out.println((tb2 - ta2) + " ms.");
System.out.println("Sorted arrays equal: " +
Arrays.equals(array1, array2));
System.out.println("");
////
System.out.println("-- Presorted data demo --");
array1 = getPresortedIntegerArray(ARRAY_LENGTH);
array2 = array1.clone();
System.out.print("My natural merge sort: ");
ta1 = System.currentTimeMillis();
NaturalMergesort.sort(array2, FROM_INDEX, TO_INDEX);
tb1 = System.currentTimeMillis();
System.out.println((tb1 - ta1) + " ms.");
System.out.print("java.util.Arrays.sort(): ");
ta2 = System.currentTimeMillis();
java.util.Arrays.sort(array1, FROM_INDEX, TO_INDEX);
tb2 = System.currentTimeMillis();
System.out.println((tb2 - ta2) + " ms.");
System.out.println("Sorted arrays equal: " +
Arrays.equals(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;
}
}
