Sort a Stack using Merge Sort

Sort a Stack using Merge Sort.

---

Lets see how to sort a stack using merge sort which uses divide and conquer recursive algorithm.

I recommend reading Merge sort first before proceeding.

Also, check Merge sort article on linked list that will help in understanding Merge sort and this article better.

Lets see sample input and output for better understanding:

Sort a Stack using Merge Sort in Java

Algorithm

---

Merge sort uses divide and conquer algorithm that is it first divide(break) the array into two parts recursively until only one element is left, once there is no more element left, It starts merging the broken arrays but while merging it will sort the broken array pieces so that the complete array gets sorted.

Check the image below to understand how Divide and Conquer algorithm works.

 

Merge sort in Java

Merge sort uses recursion, so we will also use the similar approach to sort the stack using recursion.

1. Break the stack into two parts by using two temporary stack.
2. When only one element remains on a Stack, Merge it.

Java Program to Sort a Stack using Merge Sort

---

package com.javabypatel;

import java.util.Stack;

public class SortStack {

    public static void main(String args[]) {
        Stack stack = new Stack();
        stack.push(5);
        stack.push(9);
        stack.push(1);
        stack.push(4);
        stack.push(2);
        stack.push(2);
        stack.push(-1);
        stack.push(100);
        stack.push(0);

        sort(stack);

        System.out.println(stack);
    }

    private static void sort(Stack stack) {
        Stack s1 = new Stack();
        Stack s2 = new Stack();

        while (stack.size() != 0) {
            if (stack.size() % 2 == 0) {
                s1.push(stack.pop());
            } else {
                s2.push(stack.pop());
            }
        }

        if (s1.size() > 1) {
            sort(s1);
        }

        if (s2.size() > 1) {
            sort(s2);
        }

        merge(s1, s2, stack);
    }

    private static void merge(Stack s1, Stack s2, Stack stack) {
        Stack mergedStack = new Stack();
        while (!s1.isEmpty() && !s2.isEmpty()) {
            if ((Integer) s1.peek() < (Integer) s2.peek()) {
                mergedStack.push(s2.pop());
            } else {
                mergedStack.push(s1.pop());
            }
        }

        while (!s1.isEmpty()) {
            mergedStack.push(s1.pop());
        }

        while (!s2.isEmpty()) {
            mergedStack.push(s2.pop());
        }

        while (!mergedStack.isEmpty()) {
            stack.push(mergedStack.pop());
        }
    }
}

You may also like to see

---

Sort Linked list using Merge sort

Bubble Sort

Heap Sort

Selection Sort

Insertion Sort

---

How ConcurrentHashMap works and ConcurrentHashMap interview questions

How Much Water Can A Bar Graph with different heights can Hold

Interview Questions-Answer Bank

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.