# Sorting array using Stacks

Given an array of elements, task is to sort these elements using stack.

Prerequisites : Stacks

Examples :

```Input :  8 5 7 1 9 12 10
Output : 1 5 7 8 9 10 12
Explanation :
Output is sorted element set

Input :  7 4 10 20 2 5 9 1
Output : 1 2 4 5 7 9 10 20
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We basically use Sort a stack using a temporary stack. Then we put sorted stack elements back to array.

## C++

 `// C++ program to sort an array using stack ` `#include ` `using` `namespace` `std; ` ` `  `// This function return the sorted stack ` `stack<``int``> sortStack(stack<``int``> input) ` `{ ` `    ``stack<``int``> tmpStack; ` ` `  `    ``while` `(!input.empty()) ` `    ``{ ` `        ``// pop out the first element ` `        ``int` `tmp = input.top(); ` `        ``input.pop(); ` ` `  `        ``// while temporary stack is not empty ` `        ``// and top of stack is smaller than temp ` `        ``while` `(!tmpStack.empty() && ` `                ``tmpStack.top() < tmp) ` `        ``{ ` `            ``// pop from temporary stack and ` `            ``// push it to the input stack ` `            ``input.push(tmpStack.top()); ` `            ``tmpStack.pop(); ` `        ``} ` ` `  `        ``// push temp in tempory of stack ` `        ``tmpStack.push(tmp); ` `    ``} ` ` `  `    ``return` `tmpStack; ` `} ` ` `  `void` `sortArrayUsingStacks(``int` `arr[], ``int` `n) ` `{ ` `    ``// Push array elements to stack ` `    ``stack<``int``> input; ` `    ``for` `(``int` `i=0; i tmpStack = sortStack(input); ` ` `  `    ``// Put stack elements in arrp[] ` `    ``for` `(``int` `i=0; i

## Java

 `// Java program to sort an  ` `// array using stack ` `import` `java.io.*; ` `import` `java.util.*; ` ` `  `class` `GFG ` `{ ` `    ``// This function return ` `    ``// the sorted stack ` `    ``static` `Stack sortStack(Stack input) ` `    ``{ ` `        ``Stack tmpStack =  ` `                       ``new` `Stack(); ` `     `  `        ``while` `(!input.empty()) ` `        ``{ ` `            ``// pop out the ` `            ``// first element ` `            ``int` `tmp = input.peek(); ` `            ``input.pop(); ` `     `  `            ``// while temporary stack is  ` `            ``// not empty and top of stack ` `            ``// is smaller than temp ` `            ``while` `(!tmpStack.empty() && ` `                    ``tmpStack.peek() < tmp) ` `            ``{ ` `                ``// pop from temporary  ` `                ``// stack and push it  ` `                ``// to the input stack ` `                ``input.push(tmpStack.peek()); ` `                ``tmpStack.pop(); ` `            ``} ` `     `  `            ``// push temp in ` `            ``// tempory of stack ` `            ``tmpStack.push(tmp); ` `        ``} ` `     `  `        ``return` `tmpStack; ` `    ``} ` `     `  `    ``static` `void` `sortArrayUsingStacks(``int` `[]arr,  ` `                                     ``int` `n) ` `    ``{ ` `        ``// push array elements ` `        ``// to stack ` `        ``Stack input =  ` `                       ``new` `Stack(); ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``input.push(arr[i]); ` `     `  `        ``// Sort the temporary stack ` `        ``Stack tmpStack =  ` `                       ``sortStack(input); ` `     `  `        ``// Put stack elements ` `        ``// in arrp[] ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `        ``{ ` `            ``arr[i] = tmpStack.peek(); ` `            ``tmpStack.pop(); ` `        ``} ` `    ``} ` `     `  `    ``// Driver Code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `[]arr = {``10``, ``5``, ``15``, ``45``}; ` `        ``int` `n = arr.length; ` `     `  `        ``sortArrayUsingStacks(arr, n); ` `     `  `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``System.out.print(arr[i] + ``" "``); ` `    ``} ` `} ` ` `  `// This code is contributed by  ` `// Manish Shaw(manishshaw1) `

## C#

 `// C# program to sort an  ` `// array using stack ` `using` `System; ` `using` `System.Collections.Generic; ` ` `  `class` `GFG ` `{ ` `    ``// This function return ` `    ``// the sorted stack ` `    ``static` `Stack<``int``> sortStack(Stack<``int``> input) ` `    ``{ ` `        ``Stack<``int``> tmpStack = ``new` `Stack<``int``>(); ` `     `  `        ``while` `(input.Count != 0) ` `        ``{ ` `            ``// pop out the ` `            ``// first element ` `            ``int` `tmp = input.Peek(); ` `            ``input.Pop(); ` `     `  `            ``// while temporary stack is  ` `            ``// not empty and top of stack ` `            ``// is smaller than temp ` `            ``while` `(tmpStack.Count != 0 && ` `                    ``tmpStack.Peek() < tmp) ` `            ``{ ` `                ``// pop from temporary  ` `                ``// stack and push it  ` `                ``// to the input stack ` `                ``input.Push(tmpStack.Peek()); ` `                ``tmpStack.Pop(); ` `            ``} ` `     `  `            ``// push temp in ` `            ``// tempory of stack ` `            ``tmpStack.Push(tmp); ` `        ``} ` `     `  `        ``return` `tmpStack; ` `    ``} ` `     `  `    ``static` `void` `sortArrayUsingStacks(``int` `[]arr,  ` `                                     ``int` `n) ` `    ``{ ` `        ``// Push array elements ` `        ``// to stack ` `        ``Stack<``int``> input = ``new` `Stack<``int``>(); ` `        ``for` `(``int` `i = 0; i tmpStack = sortStack(input); ` `     `  `        ``// Put stack elements in arrp[] ` `        ``for` `(``int` `i = 0; i < n; i++) ` `        ``{ ` `            ``arr[i] = tmpStack.Peek(); ` `            ``tmpStack.Pop(); ` `        ``} ` `    ``} ` `     `  `    ``// Driver Code ` `    ``static` `void` `Main() ` `    ``{ ` `        ``int` `[]arr = ``new` `int``[] {10, 5,  ` `                               ``15, 45}; ` `        ``int` `n = arr.Length; ` `     `  `        ``sortArrayUsingStacks(arr, n); ` `     `  `        ``for` `(``int` `i = 0; i < n; i++) ` `        ``Console.Write(arr[i] + ``" "``); ` `    ``} ` `} ` ` `  `// This code is contributed by  ` `// Manish Shaw(manishshaw1) `

Output:

```5 10 15 45
```

Time Complexity : O(n*n)