#include <iostream>
#include <stack>

using namespace std;

template<class T>
stack<T> CombiningStacks(stack<T> stack1, stack<T> stack2)
{
	stack<T> commonStack;

	while (!stack1.empty())
	{
		commonStack.push(stack1.top());
		stack1.pop();
	}

	while (!stack2.empty())
	{
		commonStack.push(stack2.top());
		stack2.pop();
	}

	return commonStack;
}

template<class T>
stack<T> Sort(stack<T> sourceStack)
{
	stack<T> stack1;
	stack<T> stack2;
	T currentTop;

	while (!sourceStack.empty())
	{
		currentTop = sourceStack.top();
		if (stack1.size() == 0)
		{
			stack1.push(currentTop);
			sourceStack.pop();
			continue;
		}

		if (currentTop >= stack1.top())
		{
			stack1.push(currentTop);
		}
		else
		{
			stack2.push(currentTop);
		}
		sourceStack.pop();
	}

	if (stack2.size() != 0)
	{
		return Sort(CombiningStacks(stack1, stack2));
	}

	return stack1;
}

int main()
{
	stack<int> sourceStack;
	int value, size;
	cout << "Enter the size of stack: ";
	cin >> size;

	if (size < 0)
	{
		cout << "ERROR: you entered a negative value!";
		system("pause");
		return -1;
	}

	cout << "Enter the values:" << endl;
	for (int i = 0; i < size; ++i)
	{
		cin >> value;
		sourceStack.push(value);
	}

	stack<int> sortedStack = Sort(sourceStack);
	cout << endl;

	cout << "Sorted stack: ";
	for (int i = 0; i < size; ++i)
	{
		cout << sortedStack.top();
		sortedStack.pop();
		cout << ' ';
	}

	system("pause");
	return 0;
}