Sort a stack using another stack

An algorithm to sort a stack using temporary stack.

We will implement a simple algorithm to sort a stack using another temporary stack in javascript. Everything will be written in ES6.

Example

Input:
5, 10 ,17, 11, 2, 23

Output:
23, 17, 11, 10, 5, 2

Implementation

• We will create a temporary stack.
• Then we will loop through while input stack is not empty.
• In each iteration if temporary stack is not empty and its top item is greater than input stack then we will swap them.

let sortStack = (stack) => {
  //create a temporary stack
  let tempStack = new Stack();
   
   //loop while stack is not empty
   while(!stack.isEmpty()){ 
     
     // pop out the first element 
     let tmp = stack.pop(); 
          
     // while temporary stack is not empty and 
     // top of stack is greater than temp 
     // change > to < for sorting in ascending order
     while(!tempStack.isEmpty() && tempStack.peek() > tmp){ 
        
        // pop from temporary stack and  
        // push it to the input stack 
        stack.push(tempStack.pop()); 
     } 
              
   // push temp in tempory of stack 
   tempStack.push(tmp); 
     
  } 
  
  return tempStack; 
}

Input:
let stack = new Stack();
stack.push(5); 
stack.push(10); 
stack.push(17); 
stack.push(11); 
stack.push(23); 
stack.push(2); 

let sorted = sortStack(stack);
while(!sorted.isEmpty()){
  console.log(sorted.pop());
}

Output:
23
17
11
10
5
2

If you want to sort in ascending order then update to this while(!tempStack.isEmpty() && tempStack.peek() < tmp).

Time complexity: O(n).
Space complexity: O(n).

Time and Space complexity

• We are looping while the input stack is not empty, so Time complexity is O(n).
• We are copying each item in temporary stack, so Space complexity is O(n).