# Sort a stack using recursion

Write a program to Sort a stack using recursion

#### Solution:

``````using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace StackOperation
{
class Program
{
public static void Main()
{
var st = new Stack<int>();
st.Push(1);
st.Push(2);
st.Push(5);
st.Push(3);
st.Push(4);

Console.WriteLine("Stack:");
foreach (var i in st)
Console.WriteLine(i);

Sort(st);

Console.WriteLine("Sort Stack");
foreach (var i in st)
Console.WriteLine(i);

}

static void Insert<T>(Stack<T> stack, T x) where T : IComparable<T>
{

if (stack.Count() == 0 || GreaterThen(x, stack.Peek()))
{
stack.Push(x);
return;
}

T temp = stack.Peek();
stack.Pop();
Insert(stack, x);
stack.Push(temp);
}

static void Sort<T>(Stack<T> stack) where T : IComparable<T>
{
if (stack.Count() > 0)
{
T x = stack.Peek();
stack.Pop();
Sort(stack);
Insert(stack, x);
}
}

static bool GreaterThen<T>(T a, T b) where T : IComparable<T>
{
return a.CompareTo(b) < 0;
}
}

public class Stack<T> : IEnumerable<T>
{

public void Push(T value)
{
}
public T Pop()
{
if (_list.Count == 0)
{
throw new InvalidOperationException("The Stack is empty");
}
var value = _list.First.Value;
_list.RemoveFirst();
return value;
}

public T Peek()
{
if (_list.Count == 0)
{
throw new InvalidOperationException("The Stack is empty");
}
return _list.First.Value;
}

public int Count()
{
return _list.Count;
}

public IEnumerator<T> GetEnumerator()
{
return _list.GetEnumerator();
}

IEnumerator IEnumerable.GetEnumerator()
{
return _list.GetEnumerator();
}
}
}

``````