public class Solution {
    /**
     * @param stack an integer stack
     * @return void
     */
    public void stackSorting(Stack<Integer> stack) {
        // Write your code here
        Stack<Integer> tmp = new Stack<Integer>();
        while (!stack.isEmpty()) {
            if (!stack.isEmpty() && (tmp.isEmpty() || tmp.peek() >= stack.peek())) {
                tmp.push(stack.peek());
                stack.pop();
            }
            else {
                int value = stack.peek(); stack.pop();
                while (!tmp.isEmpty() && tmp.peek() <= value)  {
                    stack.push(tmp.peek());
                    tmp.pop();
                }
                stack.push(value);
                while (!tmp.isEmpty()) {
                    stack.push(tmp.peek());
                    tmp.pop();
                }
            }
        }
        while (!tmp.isEmpty()) {
            stack.push(tmp.peek());
            tmp.pop();
        }
    }
}