Sorting a stack using another stack

Question

I want to know the time complexity of this algorithm which is used to sort a stack using another stack. I thought it is O(N^2) but apparently it looks more than that.

public static Stack<Integer> sort(Stack<Integer> s) {
    Stack<Integer> r = new Stack<Integer>();

    while(!s.isEmpty()) {
        int tmp = s.pop();
        while(!r.isEmpty() && r.peek() > tmp) {
            s.push(r.pop());
        }
        r.push(tmp);
    }
    return r;
}

Answer 1

If sorting stack [x_2, .., x_n] (stack grows towards right) takes t(n-1) time, sorting stack [x_1, .., x_n] time will do the following

1. Sort substack [x_2, .., x_n] of s
2. Pop x_1 to tmp
3. Transfer at most n-1 elements from r to s
4. Push x_1 to r
5. Once again process the elements transfered in step 3., but they are in such order that inner while loop while never run.

So running the algorithm on [x_1, .., x_n] will take at most t(n-1) + O(n) time. That leads to (for some constant c)

t(n) <= O(n) + t(n-1) <= c * n + t(n-1)
t(n) <= c * n + c * (n - 1) + t(n-2) <= ... <= c * (1 + 2 + ... + n)
t(n) <= c * n(n + 1) / 2 

So t(n) is O(n^2).