How to sort a Stack

Using recursion:
Sorting stack is similar to sort an array using insertion sort, in insertion sort we do insert elements at their correct position. But in stack we cannot move elements like we can in array so first we have to pop all the elements then we can start inserting them back one by one.

When we insert elements back one by one we check if peek element is smaller than current element or not, if yes we simply push the element else we pop the top element from stack and compare next top element with element we are trying to insert, we do same until we find correct position of the element.

The stack is: 15 (top), -8, 1, -5, 10 (bottom) and suppose now all elements are popped out and we will insert them back one by one (in stack last popped out element will be inserted back first so 10 will be inserted first and then -5 and so on):

10 -> 10

-5, 10 -> 10, -5

1, 10, -5 -> 10, 1, -5

-8, 10,1,-5 -> 10, 1, -5, -8

15, 10, 1, -5, -8 -> 15, 10, 1, -5, -8

Go through below implementation:

class Program
{
    static void Main(string[] args)
    {
        Stack<int> stack = new Stack<int>();
        stack.Push(10);
        stack.Push(-5);
        stack.Push(1);
        stack.Push(-8);
        stack.Push(15);

        //Sort
        Sort(stack);

        //Item
        Console.WriteLine("Sorted stack:");
        while (stack.Count > 0)
        {
            Console.WriteLine(stack.Pop());
        }

        Console.ReadLine();
    }

    static void Sort(Stack<int> stack)
    {
        //No elements left in stack
        if (stack.Count == 0)
            return;

        int element = stack.Pop();
        //Recursion
        Sort(stack);
        RearrangeAndInsert(stack, element);
    }

    static void RearrangeAndInsert(Stack<int> stack, int element)
    {
        //Insert if no elements present in stack or peek element is smaller than current element
        if (stack.Count == 0 || element >= stack.Peek())
            stack.Push(element);
        else
        {
            int temp = stack.Pop();
            RearrangeAndInsert(stack, element);
            stack.Push(temp);
        }
    }
}

Output:

Sorted stack:
15
10
1
-5
-8

Using temporary stack:

Same concept is used of insertion sort only temporary stack is used instead of recursion.

class Program
{
    static void Main(string[] args)
    {
        Stack<int> stack = new Stack<int>();
        stack.Push(10);
        stack.Push(-5);
        stack.Push(1);
        stack.Push(-8);
        stack.Push(15);

        stack = Sort(stack);

        //Item
        Console.WriteLine("Sorted stack:");
        while (stack.Count > 0)
        {
            Console.WriteLine(stack.Pop());
        }

        Console.ReadLine();
    }

    static Stack<int> Sort(Stack<int> stack)
    {
        Stack<int> temp = new Stack<int>();
        //Until all elements are moved
        while (stack.Count > 0)
        {
            var element = stack.Pop();

            //If peek element in temp stack is grater than item we want to insert
            //Pop elements from temp and push in stack until we have correct position for element
            while (temp.Count > 0 && element < temp.Peek())
            {
                stack.Push(temp.Pop());
            }
            //Push element at its right position
            temp.Push(element);
        }
        return temp;
    }
}

Sorted stack:
15
10
1
-5
-8