Sort Stack

• Time : O(n^2)
• Space : O(n)

#include <vector>
using namespace std;

void balance(vector<int>& st, int v) {
	if(st.empty() or st.back() <= v) {
		st.push_back(v);
		return;
	}
	
	int tp = st.back();
	st.pop_back();
	balance(st,v);
	st.push_back(tp);
	return;
}

vector<int> sortStack(vector<int> &st) {
  if(st.empty()) return st;
	
	int tp = st.back();
	st.pop_back();
	sortStack(st);
	
	balance(st, tp);
	
  return st;
}