we could use selection sort which needs two more stack
we could use insertion sort which needs one more stack.
//implement insertion sort
public class Solution {
public void sort(Stack<Integer> s) {
Stack<Integer> s2 = new Stack<Integer>();
while (!s.isEmpty()) {
// Insert each element in s in sorted order into s2(nondescending order)
int tmp = s.pop();
while (!s2.isEmpty() && s2.peek() > tmp) {
s.push(s2.pop());
}
s2.push(tmp);
}
//Copy the elements from s2 back into s.
while (!s2.isEmpty()) {
s.push(s2.pop());
}
}
}
