Sort a stack

"""
We use a temporary stack to keep elements in descending order.
In temp, the largest element stays at the bottom and the smallest stays on the top.
For each popped element x from the original stack, we pop all smaller elements from temp
(and push those elements back into the original stack) until x can be placed correctly, then push x into temp.
Finally, we move all elements from temp back to st to get the sorted stack.

T.C=O(N^2) because in already reverse sorted array you will have to do N^2 times.Like for every element, you will pop the temp till the end so N*N ie. O(N^2)
"""

class Solution:
    def sortStack(self, st):
        temp=[]
        while st:
            x=st.pop()
            while temp and x>temp[-1]:
                st.append(temp.pop())
            temp.append(x)
        while temp:
            st.append(temp.pop())
        return st