Untitled

// Entry function
// First Pops out all elements of stack and then
// builds the sorted stack gradually by calling insertion()
// to insert the element in its correct sorted place.
void sortStack(stack<int> &st) {

	if (st.empty()) return;

	int top = st.top();
	st.pop();
	
	sortStack(st);

	// insert the element in its correct sorted place.
	insertion(st, top);
}


// Given an element (curr) it inserts curr at its correct
// place in sorted order, similar to insertion sort.
void insertion(stack<int> &st, int curr) {
	// Found correct place for curr
	if (st.empty() || curr >= st.top()) {
		st.push(curr);
		return;
	}

	int top = st.top();
	st.pop();

	insertion(st, curr);

	st.push(top);
}