Question

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<Integer> res = new Stack<Integer>();

    static Stack<Integer> tmpStack = new Stack<Integer>();

      

    // Sorts input stack and returns

    // sorted stack.

    static void sortStack(Stack<Integer> 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<Integer> s1,

                                Stack<Integer> 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<Integer> s1 = new Stack<Integer>();

        Stack<Integer> s2 = new Stack<Integer>();

        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)

Answer 1

Generally the time complexity of the merge sort is O(nlogn) .{n:length of the stack or array}

But here we are considering two stacks let us say s1,s2 are the two stracks of length n,m

as per the question

1.we have to join or add the two stacks S1+S2 = Stack

n+m : length of the resultant Stack

2. As we know that to merge any stack or array of a particular length then the time complexity will be O(nlogn). here

n+m = length of the resultant Stack.

so, time complexity is O((m+n)log(m+n)).