Sort a stack

Use another stack r. pop the head (tmp) of the input stack s, compare it with the head in r, if the head is larger, push the head of r to s until the next value is no larger than tmp, push tmp to r.

For example:
stack s:
head 3, 9, 6, 2 tail
tmp = 3
stack r:
empty
push 3 to r
stack r:
3

tmp = 9
3 < 9
push 9 to r
stack r:
3, 9

tmp = 6
9 > 6
push 9 to s
stack s:
9, 2
3 < 6
push 6 to r
stack r
3, 6

tmp = 9
6 < 9
push 9 to r
stack r:
3, 6, 9

tmp = 2
9, 6, 3, > 2
push 9, 6, 3, to s
stack s:
3, 6, 9
push 2 to r
stack r:
2
push 3, 6, 9, to r
stack r:
2, 3, 6, 9

If the head of r is smaller than tmp, we need to push all elements in r that is larger than tmp back to s, at worst case, we will have to push all elements in r back to s, (like when tmp = 2 in the example), so this operation will take O(n). The outer loop will take another O(n) time, so in total O(n^2).

public class SortAStack {
 public static Stack sort(Stack s) {
  Stack r = new Stack ();
  while (!s.isEmpty()) {
   int tmp = s.pop();
   while(!r.isEmpty() && r.peek() > tmp) {
    s.push(r.pop());
   }
   r.push(tmp);
  }
  return r;
 }

 public static void main(String[] args) {
  Stack s = new Stack ();
  s.push(1);
  s.push(5);
  s.push(4);
  s.push(2);
  s.push(6);
  s.push(9);
  s.push(3);
  for (int i : sort(s)) {
   System.out.println(i);
  }
 }
}