For merge sort the time complexity is (nlogn),

but what if we had two unsorted stacks and wanted to but merge them into one final sorted stack! what is the time complexity then?

code

/ Java program to merge to unsorted stacks

// into a third stack in sorted way.

import java.io.*;

import java.util.*;

public class GFG {

// This is the temporary stack

static Stack res = new Stack();

static Stack tmpStack = new Stack();

// Sorts input stack and returns

// sorted stack.

static void sortStack(Stack input)

{

while (input.size() != 0)

{

// pop out the first element

int tmp = input.peek();

input.pop();

// while temporary stack is not empty and

// top of stack is greater than temp

while (tmpStack.size() != 0 &&

tmpStack.peek() > tmp)

{

// pop from temporary stack and push

// it to the input stack

input.push(tmpStack.peek());

tmpStack.pop();

}

// push temp in tempory of stack

tmpStack.push(tmp);

}

}

static void sortedMerge(Stack s1,

Stack s2)

{

// Push contents of both stacks in result

while (s1.size() != 0) {

res.push(s1.peek());

s1.pop();

}

while (s2.size() != 0) {

res.push(s2.peek());

s2.pop();

}

// Sort the result stack.

sortStack(res);

}

// main function

public static void main(String args[])

{

Stack s1 = new Stack();

Stack s2 = new Stack();

s1.push(34);

s1.push(3);

s1.push(31);

s2.push(1);

s2.push(12);

s2.push(23);

sortedMerge(s1, s2);

System.out.println("Sorted and merged stack :");

while (tmpStack.size() != 0) {

System.out.print(tmpStack.peek() + " ");

tmpStack.pop();

}

}

}

// This code is contributed by Manish Shaw

// (manishshaw1)