# How to Sort a Stack using Recursion

[Question]: Given a stack, the task is to sort it using recursion.
Input: elements present in stack from top to bottom -3 14 18 -5 30
Output: 30 18 14 -3 -5
Explanation: The given stack is sorted know 30 > 18 > 14 > -3 > -5

``````// Stack Definition Starts
public struct Stack<Element> {

private var storage: [Element] = []

public init() { }
}

extension Stack: CustomDebugStringConvertible {

public var debugDescription: String {
"""
----top----
\(storage.map { "\(\$0)" }.reversed().joined(separator: "\n"))
-----------
"""
}

public mutating func push(_ element: Element) {
storage.append(element)
}

public mutating func pop() -> Element? {
storage.popLast()
}

public func peek() -> Element? {
storage.last
}

public var isEmpty: Bool {
peek() == nil
}

}
// Stack Defination Ends

// Swift program to sort a Stack using recursion
// Note that here predefined Stack class is used  for stack operation

// Recursive Method to insert an item x in sorted way
func sortedInsert(_ s: inout Stack<Int>, _ item: Int) {
// Base case: Either stack is empty or newly inserted item is greater than top (more than all existing)
if s.isEmpty || item > s.peek()! {
// print("Peek & item is ----------- ",s.peek(), item)
s.push(item)
return
}
// If top is greater, remove the top item and recur
let temp = s.pop()
//print(" Insert Poped Item in stack---- ",temp!)
sortedInsert(&s, item);
// print("Recursion Call Now Add back temp------- ",temp!)
// Put back the top item removed earlier
s.push(temp!)
}

// Method to sort stack
func sortStack(_ s: inout Stack<Int>) {
// Base case If stack is empty return
if s.isEmpty { return }
// Remove the top item
let topItem = s.pop()
// Sort remaining stack
sortStack(&s)
// Push the top item back in sorted stack
sortedInsert(&s, topItem!)
}

var stackInput = Stack<Int>()
stackInput.push(-3)
stackInput.push(30)
stackInput.push(-5)
//stackInput.push(18)
stackInput.push(14)
print("Input---->", stackInput)
/**
Input----> ----top----
14
-5
30
-3
*/
sortStack(&stackInput);
print("Output--->", stackInput)
/**
Output---> ----top----
30
14
-3
-5
-----------
*/
``````