Stack: Merge and sort 2 unsorted array

Problem Statement:

Merge and sort 2 unsorted array

Example:

Input:

s1 = {4, 3, 2}

s2 = {7, 6}

Output:

{2, 3, 4, 6, 7}

Solution :

Take a temp stack to store the result.

Then insert elements into the both stacks into the result.

Sort the stack.

Time Complexity: O(n+m)^2
Space Complexity: O(n+m)

Code Solution

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

stack<int> sortStack(stack<int>& input)
{
	stack<int> tmpStack;

	while (!input.empty()) 
	{

		int tmp = input.top();
		input.pop();

		while (!tmpStack.empty() && tmpStack.top() > tmp) 
		{

			input.push(tmpStack.top());
			tmpStack.pop();
		}

		tmpStack.push(tmp);
	}

	return tmpStack;
}

stack<int> mergeStack(stack<int>& s1, stack<int>& s2)
{
	stack<int> res;
	while (!s1.empty()) 
	{
		res.push(s1.top());
		s1.pop();
	}
	while (!s2.empty()) 
	{
		res.push(s2.top());
		s2.pop();
	}

	return sortStack(res);
}

// main function
int main()
{
	stack<int> s1, s2;
	s1.push(5);
	s1.push(4);
	s1.push(3);

	s2.push(6);
	s2.push(2);
	s2.push(1);

	stack<int> sortedStack = mergeStack(s1, s2);
	cout << "Sorted and merged stack :\n";

	while (!sortedStack.empty()) 
	{
		cout << sortedStack.top() << " ";
		sortedStack.pop();
	}
}

Output

6 5 4 3 2 1