Sort stack in ascending order

Question

I am using two more helper stacks to sort. Kindly suggest improvements in terms of space and time.

import java.util.ArrayDeque;
import java.util.Deque;

public class SortStackAscendingOrder {

    Deque<Integer> stackhelper1 = new ArrayDeque<>();
    Deque<Integer> stackHelper2 = new ArrayDeque<>();

    public Deque<Integer> sortStack(Deque<Integer> mainStack) {
        if (mainStack.isEmpty()) {
            return null;
        }

        while (!mainStack.isEmpty()) {
            int mainItem = mainStack.pop();
            int helperItem1 = -1;
            if (!stackhelper1.isEmpty()) {
                helperItem1 = stackhelper1.peek();
            }
            if (mainItem > helperItem1) {
                // push all helperItem1 to helperItem2, till it is in ascending
                // order
                while (!stackhelper1.isEmpty() && mainItem > helperItem1) {
                    stackHelper2.push(stackhelper1.pop());
                    helperItem1 = stackhelper1.peek();
                }
                // push mainItem.
                stackhelper1.push(mainItem);
                // bring back all the helperItem2
                while (!stackHelper2.isEmpty()) {
                    stackhelper1.push(stackHelper2.pop());
                }
            } else {
                // directly push in stackhelper1
                stackhelper1.push(mainItem);
            }
        }

        return stackhelper1;

    }

}

Answer 1

Possible bug:

The following demo will throw a NullPointerException:

public static void main(String[] args) {
    Deque<Integer> stack = new ArrayDeque<>();

    stack.addLast(2);
    stack.addLast(-1);
    stack.addLast(-3);
    stack.addLast(1);

    System.out.println("Original stack: " + stack);
    SortStackAscendingOrder sorter = new SortStackAscendingOrder();

    Deque<Integer> sortedStack = sorter.sortStack(stack);

    System.out.println("Sorted original stack: " + sortedStack);

    stack.clear();
    stack.addLast(11);
    stack.addLast(8);
    stack.addLast(9);
    stack.addLast(10);

    System.out.println("Another stack: " +
            sorter.sortStack(stack));

    System.out.println("Sorted original stack again: " + sortedStack);
}

Most likely the problem above is due to the fact that you return stackhelper1, which is an essential internal facility in your algorithm.

API design:

First of all, I would consider implementing the stack sort as a static method that does not "leak" any internals. The idea here is that you sort the input stack: just like sorting methods in java.util.Arrays, all are void and modify the input arrays instead of returning a sorted copy.

All in all, I had this in mind:

public static void sortStack(Deque<Integer> mainStack) {
    Deque<Integer> stackHelper1 = new ArrayDeque<>();
    Deque<Integer> stackHelper2 = new ArrayDeque<>();

    while (!mainStack.isEmpty()) {
        int mainItem = mainStack.pop();
        int helperItem1 = -1;

        if (!stackHelper1.isEmpty()) {
            helperItem1 = stackHelper1.peek();
        }

        if (mainItem > helperItem1) {
            while (!stackHelper1.isEmpty() && mainItem > helperItem1) {
                stackHelper2.push(stackHelper1.pop());
                helperItem1 = stackHelper1.peek();
            }

            stackHelper1.push(mainItem);

            while (!stackHelper2.isEmpty()) {
                stackHelper1.push(stackHelper2.pop());
            }
        } else {
            stackHelper1.push(mainItem);
        }
    }

    mainStack.clear();
    mainStack.addAll(stackHelper1);
}

Answer 2

You should take more attention to the naming convention of Java :

Deque<Integer> stackhelper1 = new ArrayDeque<>();
Deque<Integer> stackHelper2 = new ArrayDeque<>();

The variable should be named stackHelper1, the H is what was missing. I don't like numbered variable names. It always let me wonder if it's a bad design decision or simply bad names. In this case, I think it's just a bad name, maybe try to really name it after what they are.

// push mainItem.
stackhelper1.push(mainItem);

You really don't have to state the obvious in a comment. Just by reading the line of code I can easily understand that you're pushing mainItem`, that's what the method is called. Almost all your comments are noise in the code. What would have a been a bit more useful is Javadoc to explain what the method is about and maybe expose your "algo", something like this javadoc.

    if (mainStack.isEmpty()) {
        return null;
    }

I would have really like to have been warned that using your method with an empty collection would return me null. If I passe you an empty collection, I would have expected to have an empty collection in return. Returning null just expose the user of the method to NullPointerExceptions. You should really ask yourself if returning null is a good thing, in a good number of occasion it will complicate things.

Answer 3

The null pointer exception pointed earlier can be avoided if you just do a check stackhelper1.isEmpty()

if(!stackhelper1.isEmpty())
        helperItem1 = stackhelper1.peek();

In terms of improving space complexity, there is a way to sort stack using one stack:-

private static Stack<Integer> sortWithOneStack(Stack<Integer> s1) {
    Stack<Integer> s2 = new Stack<Integer>();
    while(!s1.isEmpty()){
        int topEl = s1.pop();
        while(!s2.isEmpty() && s2.peek() > topEl){
            s1.push(s2.pop());
        }
        s2.push(topEl);
    }
    return s2;
}

You just push the element back to the original stack if that is less than the top of the other stack.

In fact, there is a way to do it without using any external stack at all. Here is the code for it.

public static void sort(Stack<Integer> st){
    if(st.isEmpty())
        return;
    int el = st.pop();
    sort(st);
    putInSortedOrder(st,el);
}

private static void putInSortedOrder(Stack<Integer> st, int el) {
    if(st.isEmpty() || st.peek() < el){
        st.add(el);
        return;
    }
    int cur = st.pop();
    putInSortedOrder(st, el);
    st.push(cur);
}

The secret is that this method uses the system stack. All the techniques are using the same logic but using different stacks.