Sort Stack

Description:

Given a stack, sort it using recursion.

解题方法：

通过递归进入stack的每一个元素，然后再用递归对当前元素与剩下的元素进行insert sort

Time Complexity：

O(n^2)

完整代码：

void insertSort(stack<int>& S, int num) {
    if(S.empty() || num >= S.top())
        S.push(num);
    else {
        int temp = S.top();
        S.pop();
        insertSort(S, num);
        S.push(temp);
    }
}

void sortStack(stack<int>& S) {
    if(S.empty())
        return;
    int temp = S.top();
    S.pop();
    sortStack(S);
    insertSort(S, temp);
}