# Sort a stack using recursion  Difficulty Level Easy
Frequently asked in Amazon Goldman Sachs IBM Kuliza Yahoo
Recursion Stack

## Problem Statement  The problem “Sort a stack using recursion” states that you are given a stack data structure. Sort its elements using recursion. Only the below-listed functions of the stack can be used –

• push(element) – to insert the element in the stack.
• pop() – pop() – to remove/delete the element at the top of the given stack.
• isEmpty() – to check if there is any element in the stack or not.
• top() – to peek/see the element at the top of the given stack.

## Example  `9 4 2 -1 6 20`
`20 9 6 4 2 -1`

Explanation: Since the stack is sorted in ascending order. The maximum element comes at the top. Because stack is LIFO data structure, the output seems to be in descending order.

`2 1 4 3 6 5`
`6 5 4 3 2 1`

## Algorithm  1. Initialize a stack and push elements in it.
2. Create a function to insert the elements in sorted order in the stack which accepts a stack and an element as a parameter. Check if the stack is empty or the given element is greater than the element at the top of the stack, push the element in the stack and return.
3. Create a temporary variable and store the top of the stack in it. Pop the element at the top of the stack and make the recursive call to the function itself. Push the temporary variable in the stack.
4. Similarly, create a function sort() that accepts a stack as a parameter. Check if the stack is not empty, create a variable x, and store the top of the stack in it. Pop the element at the top of the stack. Make a recursive call to the function itself. Call the function to insert the elements in sorted order in the stack.
5. Call the sort function in the main().
6. Create a function to print the sorted stack which accepts a stack as the parameter. Traverse while the stack is not empty, print the data of the stack and move to the next element.
Check if stack elements are pairwise consecutive

## Code  ### C++ Program to sort a stack using recursion

```#include <iostream>
using namespace std;

struct stack{
int data;
struct stack *next;
};

void initStack(struct stack **s){
*s = NULL;
}

int isEmpty(struct stack *s){
if(s == NULL){
return 1;
}
return 0;
}

void push(struct stack **s, int x){

struct stack *p = (struct stack *)malloc(sizeof(*p));

if(p == NULL){
return;
}

p->data = x;
p->next = *s;
*s = p;
}

int pop(struct stack **s){
int x;
struct stack *temp;

x = (*s)->data;
temp = *s;
(*s) = (*s)->next;
free(temp);

return x;
}

int top(struct stack *s){
return (s->data);
}

void InsertWithSort(struct stack **s, int x){

if(isEmpty(*s) or x > top(*s)){
push(s, x);
return;
}

int temp = pop(s);
InsertWithSort(s, x);

push(s, temp);
}

void sort(struct stack **s){

if(!isEmpty(*s)){
int x = pop(s);

sort(s);

InsertWithSort(s, x);
}
}

void print(struct stack *s){
while(s){
cout<<s->data<<" ";
s = s->next;
}
}

int main(){
struct stack *top;

initStack(&top);

push(&top, 9);
push(&top, 4);
push(&top, 2);
push(&top, -1);
push(&top, 6);
push(&top, 20);

sort(&top);

print(top);

return 0;
}```
`20 9 6 4 2 -1`

### Java Program to sort a stack using recursion

```import java.util.ListIterator;
import java.util.Stack;

class SortStack{

static void InsertWithSort(Stack<Integer> s, int x){
if (s.isEmpty() || x > s.peek()){
s.push(x);
return;
}

int temp = s.pop();
InsertWithSort(s, x);

s.push(temp);
}

static void sort(Stack<Integer> s){
if(!s.isEmpty()){
int x = s.pop();

sort(s);

InsertWithSort(s, x);
}
}

static void print(Stack<Integer> s){
ListIterator<Integer> lt = s.listIterator();

while(lt.hasNext()){
lt.next();
}

while(lt.hasPrevious()){
System.out.print(lt.previous()+" ");
}
}

public static void main(String[] args){
Stack<Integer> s = new Stack<>();

s.push(9);
s.push(4);
s.push(2);
s.push(-1);
s.push(6);
s.push(20);

sort(s);

print(s);

}
}```
`20 9 6 4 2 -1`

## Complexity Analysis  ### Time Complexity

O(N^2) where n is the number of elements in the stack. Because when we push the element in the stack we may end up removing all the elements which are currently present in the stack and then insert it. This case occurs if the input is in decreasing order.