Code 101: Sort a Stack using Recursion

Question:

Given a stack, sort it using recursion. Use of any loop constructs like while, for..etc is not allowed.

Solution:

This question follows the same algorithm as Sort an Array using recursion. So I would suggest you go through the post and try it once.

I have added the code and the call order because once go through it you'll see the code is similar.

package stack.queue;
import java.util.Stack;
public class SortStackWithRecursion {
    static Stack stack;
    public static void sort() {
        if (!stack.isEmpty()) {
            int temp = stack.pop();
            sort();
            insert(temp);
        }
    }
    private static void insert(int value) {
        if (stack.isEmpty() || stack.peek() < value) {
            stack.push(value);
        } else {
            int temp = stack.pop();
            insert(value);
            stack.push(temp);
        }
    }
    public static void main(String[] args) {
        stack = new Stack<>();
        stack.add(12112);
        stack.add(21);
        stack.add(300);
        stack.add(41);
        stack.add(52);
        for (int i : stack) {
            System.out.print(i + " ,");
        }
        System.out.println("\n>>>");
        sort();
        System.out.println("<<<");
        for (int i : stack) {
            System.out.print(i + " ,");
        }
    }
}

Sort [12112, 21, 300, 41, 52] Stack Size: 5
Sort [12112, 21, 300, 41] Stack Size: 4
Sort [12112, 21, 300] Stack Size: 3
Sort [12112, 21] Stack Size: 2
Sort [12112] Stack Size: 1
Insert [] Stack Size: 0
Inserting Value: 12112
Insert [12112] Stack Size: 1
Insert [] Stack Size: 0
Inserting Value: 21
Inserting Value: 12112
Insert [21, 12112] Stack Size: 2
Insert [21] Stack Size: 1
Inserting Value: 300
Inserting Value: 12112
Insert [21, 300, 12112] Stack Size: 3
Insert [21, 300] Stack Size: 2
Insert [21] Stack Size: 1
Inserting Value: 41
Inserting Value: 300
Inserting Value: 12112
Insert [21, 41, 300, 12112] Stack Size: 4
Insert [21, 41, 300] Stack Size: 3
Insert [21, 41] Stack Size: 2
Inserting Value: 52
Inserting Value: 300
Inserting Value: 12112

#HappyCoding