Sorting a Stack in ascending order Here's my implementation of sorting a stack in ascending order. The problem statement is as follows :


  Write a program to sort a stack in ascending order (with biggest items on top).
  You may use at most one additional stack to hold items, but you may not copy
  the elements into any other data structure (such as an array). The stack supports
  the following operations: push, pop, peek, and isEmpty.


My Algorithm :
Take two stacks I'll call it myStack and helperStack.


If helper stack is empty, simply pop from myStack and push it to helperStack.
If top of helperStack is less than the top of myStack, then pop it from myStack and push it to helperStack. Recurse on two Stacks.
If top of helperStack is less greater than the top of myStack then, recursively pop from helperStack and push it to myStack until the condition is violated. Finally push it to the right position.
End if myStack isEmpty.


Code

static class Node{
    int data;
    Node next;

    Node(int data){
        this.data = data;
    }
}

static class Stack{
    Node top;
    String name;
    Stack nextStack;

    public boolean isEmpty(){
        return top==null;
    }

    Stack(String name){
        this.name = name;
    }


    public int pushTo(Stack anotherStack){
        int popped = this.pop();
        anotherStack.push(popped);
        return popped;
    }


    public void _push(int data){
        System.out.println("Pushing : " + data + " to " + this.name);
        if(top==null){
            top = new Node(data);
        }else{
            Node temp = new Node(data);
            temp.next = top;
            top = temp;
        }

    }

    public void push(int... data){
        for(int i : data){
            this._push(i);
        }
    }

    public int pop(){
        if(top==null){
            System.out.println("Error : Stack is empty!!");
            return -1;
        }
        System.out.println("Popping " + top.data + " from " + this.name);
        Node toRet = top;
        top = top.next;
        return toRet.data;
    }   

    public int peek(){
        return top.data;
    }

    public void printStack(){
        Node temp = top;
        while(temp.next!=null){
            System.out.print(temp.data + "-&gt;");
            temp = temp.next;
        }
        System.out.println(temp.data);
    }

}//End of Class Stack


public static void sortStack(Stack myStack, Stack helperStack, int curr){
    if(myStack.isEmpty()){
        return;
    }
    if(curr==-1)
        curr = myStack.pop();
    if(helperStack.isEmpty() || curr &gt; helperStack.peek()){
        helperStack.push(curr);
        sortStack(myStack, helperStack, -1);
    }else{
        helperStack.pushTo(myStack);
        sortStack(myStack, helperStack, curr);
    }
}

public static void main(String[] args) {
    Stack someStack = new Stack("someStack");
    Stack helperStack = new Stack("helperStack");
    someStack.push(1,2,3, 200, 4, 22);
    someStack.printStack();
    sortStack(someStack, helperStack, -1);
    helperStack.printStack();
}


Analysis

In worst case , the number of steps executed : n (for popping it out from helperStack) + 1 (pushing the current element at right place) + n (for popping elements out from myStack).
So,
T(n) = 2n + 1

Solving this recurrence, I get a complexity of \$\theta\$(\$2^n\$)
Hence, the algorithm runs in exponential time. Is there any way I could make it faster without violating the condition?

Feel free to suggest and criticize :)
public void _push(int data){


You've named a function in a way that suggests it shouldn't be used, but keep it public then support it via push(int... anyway.

There's no need to name your functions something different here; Java can do overloading just fine. If you name your function push, java knows when it needs to call push(int data) or push(int... data).

public int peek(){
    return top.data;
}


Your peek function causes a NullPointerException if the stack is empty. Consider returning -1 as well, since that's the value you use for "there was no data".