(See the previous iteration.)
Now I have implemented a stack merge sort that does not have to reverse every substack after sorting it, and it allocates the two auxiliary stacks only once prior to the actual sorting. Now I have this:
StackMergesort.java:
import java.util.Collections;
import java.util.Random;
import java.util.Stack;
import java.util.stream.IntStream;
public class StackMergesort {
//// ALREADY REVIEWED, PLEASE IGNORE
public static <E extends Comparable<? super E>>
void sort(final Stack<E> stack) {
if (stack.size() < 2) {
// Trivially sorted.
return;
}
if (stack.size() == 2) {
final E element1 = stack.pop();
final E element2 = stack.pop();
if (element1.compareTo(element2) < 0) {
stack.push(element2);
stack.push(element1);
} else {
stack.push(element1);
stack.push(element2);
}
return;
}
final int size = stack.size();
final int auxStackLength = size / 2;
final Stack<E> aux1 = new Stack<>();
final Stack<E> aux2 = new Stack<>();
for (int i = 0; i < auxStackLength; ++i) {
aux1.push(stack.pop());
}
while (!stack.isEmpty()) {
aux2.push(stack.pop());
}
sort(aux1);
sort(aux2);
Collections.<E>reverse(aux1);
Collections.<E>reverse(aux2);
// Merge.
while (!aux1.isEmpty() && !aux2.isEmpty()) {
if (aux1.peek().compareTo(aux2.peek()) > 0) {
stack.push(aux1.pop());
} else {
stack.push(aux2.pop());
}
}
while (!aux1.isEmpty()) { stack.push(aux1.pop()); }
while (!aux2.isEmpty()) { stack.push(aux2.pop()); }
}
// ALREADY REVIEWED, PLEASE IGNORE
public static <E extends Comparable<? super E>>
void sort2(final Stack<E> stack) {
sort2(stack, new Stack<E>(), new Stack<E>());
}
// ALREADY REVIEWED, PLEASE IGNORE
private static <E extends Comparable<? super E>>
void sort2(final Stack<E> stack,
final Stack<E> aux1,
final Stack<E> aux2) {
if (stack.size() < 2) {
return;
}
if (stack.size() == 2) {
final E element1 = stack.pop();
final E element2 = stack.pop();
if (element1.compareTo(element2) < 0) {
stack.push(element2);
stack.push(element1);
} else {
stack.push(element1);
stack.push(element2);
}
return;
}
final int size = stack.size();
final int auxStackLength = size / 2;
for (int i = 0; i < auxStackLength; ++i) {
aux1.push(stack.pop());
}
while (!stack.isEmpty()) {
aux2.push(stack.pop());
}
sort(aux1);
sort(aux2);
Collections.<E>reverse(aux1);
Collections.<E>reverse(aux2);
// Merge.
while (!aux1.isEmpty() && !aux2.isEmpty()) {
if (aux1.peek().compareTo(aux2.peek()) > 0) {
stack.push(aux1.pop());
} else {
stack.push(aux2.pop());
}
}
while (!aux1.isEmpty()) { stack.push(aux1.pop()); }
while (!aux2.isEmpty()) { stack.push(aux2.pop()); }
}
// REVIEW THIS METHOD AND EVERYTHING IT CALLS DIRECTLY OR NOT.
public static <E extends Comparable<? super E>>
void sort3(final Stack<E> stack) {
if (stack.size() < 2) {
return;
}
sort3Ascending(stack, new Stack<>(), new Stack<>(), stack.size());
}
private static <E extends Comparable<? super E>>
void sort2ElementsAscending(final Stack<E> stack) {
final E topElement = stack.pop();
final E bottomElement = stack.peek();
if (topElement.compareTo(bottomElement) > 0) {
stack.pop();
stack.push(topElement);
stack.push(bottomElement);
} else {
stack.push(topElement);
}
}
private static <E extends Comparable<? super E>>
void sort2ElementsDescending(final Stack<E> stack) {
final E topElement = stack.pop();
final E bottomElement = stack.peek();
if (bottomElement.compareTo(topElement) > 0) {
stack.pop();
stack.push(topElement);
stack.push(bottomElement);
} else {
stack.push(topElement);
}
}
private static <E extends Comparable<? super E>>
void sort3Ascending(final Stack<E> stack,
final Stack<E> aux1,
final Stack<E> aux2,
final int rangeLength) {
if (rangeLength == 1) {
return;
} else if (rangeLength == 2) {
sort2ElementsAscending(stack);
return;
}
final int auxLeftStackSize = rangeLength >>> 1;
final int auxRightStackSize = rangeLength - auxLeftStackSize;
for (int i = 0; i < auxLeftStackSize; ++i) {
aux1.push(stack.pop());
}
for (int i = 0; i < auxRightStackSize; ++i) {
aux2.push(stack.pop());
}
sort3Descending(aux1, aux2, stack, auxLeftStackSize);
sort3Descending(aux2, aux1, stack, auxRightStackSize);
int leftCounter = 0;
int rightCounter = 0;
while (leftCounter < auxLeftStackSize
&& rightCounter < auxRightStackSize) {
if (aux1.peek().compareTo(aux2.peek()) > 0) {
stack.push(aux1.pop());
leftCounter++;
} else {
stack.push(aux2.pop());
rightCounter++;
}
}
while (leftCounter++ < auxLeftStackSize) { stack.push(aux1.pop()); }
while (rightCounter++ < auxRightStackSize) { stack.push(aux2.pop()); }
}
private static <E extends Comparable<? super E>>
void sort3Descending(final Stack<E> stack,
final Stack<E> aux1,
final Stack<E> aux2,
final int rangeLength) {
if (rangeLength == 1) {
return;
} else if (rangeLength == 2) {
sort2ElementsDescending(stack);
return;
}
final int auxLeftStackSize = rangeLength >>> 1;
final int auxRightStackSize = rangeLength - auxLeftStackSize;
for (int i = 0; i < auxLeftStackSize; ++i) {
aux1.push(stack.pop());
}
for (int i = 0; i < auxRightStackSize; ++i) {
aux2.push(stack.pop());
}
sort3Ascending(aux1, aux2, stack, auxLeftStackSize);
sort3Ascending(aux2, stack, aux1, auxRightStackSize);
int leftCounter = 0;
int rightCounter = 0;
while (leftCounter < auxLeftStackSize && rightCounter < auxRightStackSize) {
if (aux2.peek().compareTo(aux1.peek()) > 0) {
stack.push(aux1.pop());
leftCounter++;
} else {
stack.push(aux2.pop());
rightCounter++;
}
}
while (leftCounter++ < auxLeftStackSize) { stack.push(aux1.pop()); }
while (rightCounter++ < auxRightStackSize) { stack.push(aux2.pop()); }
}
public static <E extends Comparable<? super E>>
boolean isSorted(final Stack<E> stack) {
if (stack.size() < 2) {
// Trivially sorted.
return true;
}
E previous = stack.pop();
while (!stack.isEmpty()) {
E current = stack.pop();
if (previous.compareTo(current) > 0) {
return false;
}
previous = current;
}
return true;
}
private static final int STACK_LENGTH = 5_000_000;
private static final int WARM_UP_ITERATIONS = 200;
private static final int WARM_UP_STACK_LENGTH = 10_000;
public static void main(final String[] args) {
final long seed = System.nanoTime();
final Random random = new Random(seed);
final Stack<Integer> stack = createRandomIntegerStack(10, random);
// Note: the topmost element of a stack is the rightmost
// one in the output.
System.out.println("Seed = " + seed);
System.out.println("Before: " + stack);
sort3(stack);
System.out.println("After: " + stack);
System.out.println("Sorted: " + isSorted(stack));
System.out.println("--- Performance demo ---");
System.out.println("[STATUS] Warming up...");
warmup();
System.out.println("[STATUS] Warming up done.");
final Stack<Integer> stack1 = createRandomIntegerStack(STACK_LENGTH, random);
final Stack<Integer> stack2 = copy(stack1);
final Stack<Integer> stack3 = copy(stack1);
long startTime = System.nanoTime();
sort(stack1);
long endTime = System.nanoTime();
System.out.printf("Original sort in %.2f milliseconds.\n",
(endTime - startTime) / 1e6);
startTime = System.nanoTime();
sort2(stack2);
endTime = System.nanoTime();
System.out.printf("Improved sort in %.2f milliseconds.\n",
(endTime - startTime) / 1e6);
startTime = System.nanoTime();
sort3(stack3);
endTime = System.nanoTime();
System.out.printf("Most improved sort in %.2f milliseconds.\n",
(endTime - startTime) / 1e6);
System.out.println("Result stacks are equal: " +
(stack1.equals(stack2) && stack1.equals(stack3)));
}
private static Stack<Integer>
createRandomIntegerStack(final int size, final Random random) {
final Stack<Integer> stack = new Stack<>();
IntStream.range(0, size)
.forEach((e) -> { stack.add(random.nextInt(100));});
return stack;
}
private static Stack<Integer> copy(final Stack<Integer> stack) {
final Stack<Integer> copy = new Stack<>();
for (int i = 0; i < stack.size(); ++i) {
copy.push(stack.get(i));
}
return copy;
}
private static void warmup() {
final Random random = new Random();
for (int iteration = 0; iteration < WARM_UP_ITERATIONS; ++iteration) {
Stack<Integer> stack1 =
createRandomIntegerStack(WARM_UP_STACK_LENGTH, random);
Stack<Integer> stack2 = copy(stack1);
Stack<Integer> stack3 = copy(stack1);
sort(stack1);
sort2(stack2);
sort3(stack3);
}
}
}
When sorting random integer stacks of length 5 million I get the following performance figures:
Seed = 121163108948655 Before: [94, 94, 48, 19, 15, 73, 85, 63, 13, 5] After: [94, 94, 85, 73, 63, 48, 19, 15, 13, 5] Sorted: true --- Performance demo --- [STATUS] Warming up... [STATUS] Warming up done. Original sort in 11688.47 milliseconds. Improved sort in 8052.73 milliseconds. Most improved sort in 7268.04 milliseconds. Result stacks are equal: true
As always, any critique (algorithm, coding conventions, warming up, to name a few) is much appreciated.
sort2()insort2(Stack<E>, Stack<E>, Stack<E>)(really reviewed?). \$\endgroup\$ – greybeard May 13 '16 at 4:51sort2()in the question linked: hassort2()been reviewed, can I find that on CR? Too short for an answer: (doc)comments; prefer Deque overjava.util.Stack(and use the size parameter constructing anArrayDeque); usingComparablein favour ofComparatormakes it difficult to unify the As/Descending twins; if the purpose (none found beyonduse as little aid from JDK library as possible) didn't included use as few stacks as feasible, try distributing runs to more than one stack in all but the final merges; try not emptying the "source stack" that doesn't empty 1st. \$\endgroup\$ – greybeard May 13 '16 at 8:10