Mergesorting a stack in Java (See the next iteration.)

I have this small program for sorting a stack using mergesort. Basically, the aim was to use as little aid from JDK library as possible. See what I have:

StackMergesort.java:

import java.util.Collections;
import java.util.Random;
import java.util.Stack;
import java.util.stream.IntStream;

public class StackMergesort {

    public static &lt;E extends Comparable&lt;? super E&gt;&gt; 
        void sort(final Stack&lt;E&gt; stack) {
        if (stack.size() &lt; 2) {
            // Trivially sorted.
            return;
        }

        if (stack.size() == 2) {
            final E element1 = stack.pop();
            final E element2 = stack.pop();

            if (element1.compareTo(element2) &lt; 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&lt;E&gt; aux1 = new Stack&lt;&gt;();
        final Stack&lt;E&gt; aux2 = new Stack&lt;&gt;();

        for (int i = 0; i &lt; auxStackLength; ++i) {
            aux1.push(stack.pop());
        }

        while (!stack.isEmpty()) {
            aux2.push(stack.pop());
        }

        sort(aux1);
        sort(aux2);

        Collections.&lt;E&gt;reverse(aux1);
        Collections.&lt;E&gt;reverse(aux2);

        // Merge.
        while (!aux1.isEmpty() &amp;&amp; !aux2.isEmpty()) {
            if (aux1.peek().compareTo(aux2.peek()) &gt; 0) {
                stack.push(aux1.pop());
            } else {
                stack.push(aux2.pop());
            }
        }

        while (!aux1.isEmpty()) { stack.push(aux1.pop()); }
        while (!aux2.isEmpty()) { stack.push(aux2.pop()); }
    }

    public static &lt;E extends Comparable&lt;? super E&gt;&gt; boolean isSorted(final Stack&lt;E&gt; stack) {
        if (stack.size() &lt; 2) {
            // Trivially sorted.
            return true; 
        }

        E previous = stack.pop();

        while (!stack.isEmpty()) {
            E current = stack.pop();

            if (previous.compareTo(current) &gt; 0) {
                return false;
            }

            previous = current;
        }

        return true;
    }

    public static void main(final String[] args) {
        final long seed = System.nanoTime();
        final Random random = new Random(seed);
        final Stack&lt;Integer&gt; stack = createRandomIntegerStack(20, 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);
        sort(stack);
        System.out.println("After:  " + stack);
        System.out.println("Sorted: " + isSorted(stack));
    }

    private static Stack&lt;Integer&gt; 
        createRandomIntegerStack(final int size, final Random random) {
        final Stack&lt;Integer&gt; stack = new Stack&lt;&gt;();
        IntStream.range(0, size)
                 .forEach((e) -&gt; { stack.add(random.nextInt(100));});
        return stack;
    }
}


Any critique much appreciated.
Not too many things to remark.

I'll review regarding this assumption : Stack is to be viewed as a Stack datastructure, only peek, pop, push, size and isEmpty are to be used. The fact that java.util.Stack is also a List is not to be exploited.


The sort() methods structure falls into three cases size is 1, size is 2, and size is greater than 2. It would help readability to extract the second and third case as separate methods :

public static &lt;E extends Comparable&lt;? super E&gt;&gt; void sort(final Stack&lt;E&gt; stack) {
    if (stack.size() &lt; 2) {
        // Trivially sorted.
        return;
    }

    if (stack.size() == 2) {
        sortSize2Stack(stack);
        return;
    }

    sortLargerStack(stack);
}

For the size two stack case you can avoid popping the second element if it's greater than the first.
These variables are used only once each :

final int size = stack.size();
final int auxStackLength = size / 2;


They should be inlined.
Help from the java libraries could be avoided here by rolling your own reverse method (I guess it just fell outside the focus of the exercise for you)

Collections.&lt;E&gt;reverse(aux1);
Collections.&lt;E&gt;reverse(aux2);

You could merge in reverse order, and call reverse only once, on the merged stack. To me that seems more readable, but it's a judgement call I guess.