Sort a stack using recursion - GeeksforGeeks

Related: Sorting a given stack using one additional stack
Sort a stack using recursion - GeeksforGeeks
Given a stack, sort it using recursion. Use of any loop constructs like while, for..etc is not allowed.

The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one in sorted order. Here sorted order is important.

sortStack(stack S)
 if stack is not empty:
  temp = pop(S);  
  sortStack(S); 
  sortedInsert(S, temp);

Below algorithm is to insert element is sorted order:

sortedInsert(Stack S, element)
 if stack is empty OR element > top element
  push(S, elem)
 else
  temp = pop(S)
  sortedInsert(S, element)
  push(S, temp)

    // Recursive Method to insert an item x in sorted way

    static void sortedInsert(Stack<Integer> s, int x)

    {

        // Base case: Either stack is empty or newly inserted

        // item is greater than top (more than all existing)

        if (s.isEmpty() || x > s.peek())

        {

            s.push(x);

            return;

        }

       

        // If top is greater, remove the top item and recur

        int temp = s.pop();

        sortedInsert(s, x);

       

        // Put back the top item removed earlier

        s.push(temp);

    }

       

    // Method to sort stack

    static void sortStack(Stack<Integer> s)

    {

        // If stack is not empty

        if (!s.isEmpty())

        {

            // Remove the top item

            int x = s.pop();

       

            // Sort remaining stack

            sortStack(s);

       

            // Push the top item back in sorted stack

            sortedInsert(s, x);

        }

    }




Read full article from Sort a stack using recursion - GeeksforGeeks