(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 = 121163108948655Before: [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: trueAs always, any critique (algorithm, coding conventions, warming up, to name a few) is much appreciated.
Mergesorting a stack in Java - a new algorithm
java;algorithm;stack;mergesort