---
# System prepended metadata

title: 'Stack Medium #3: Sort Stack'
tags: [medium, Stack]

---

# Stack Medium #3: Sort Stack

###### tags:`Stack` `medium`

## Issue

Write a function that takes in an array of integers representing a stack, recursively sorts the stack in place (i.e., doesn't create a brand new array), and returns it.

The array must be treated as a stack, with the end of the array as the top of the stack. Therefore, you're only allowed to
- Pop elements from the top of the stack by removing elements from the end of the array using the built-in `.pop()` method in your programming language of choice.
- Push elements to the top of the stack by appending elements to the end of the array using the built-in `.append()` method in your programming language of choice.
- Peek at the element on top of the stack by accessing the last element in the array.
 
You're not allowed to perform any other operations on the input array, including accessing elements (except for the last element), moving elements, etc.. You're also not allowed to use any other data structures, and your solution must be recursive.

## Sample Input

```
stack = [-5, 2, -2, 4, 3, 1]
```

## Sample Output

```
[-5, -2, 1, 2, 3, 4]
```

## Hints

:::spoiler Hint 1
If you had to insert a single item into an already sorted stack, all the while abiding by the constraints of this problem, how would you do that?
:::

<br />

:::spoiler Hint 2
Inserting a single item in an already sorted stack is fairly simple: you can pop elements off of the stack until you find an element that's smaller than or equal to the value that you want to add. Then, you can push that value on top of the stack and reinsert all the previously popped items back on top of the stack in the reverse order in which you popped them off. The resulting stack will still be sorted.
:::

<br />

:::spoiler Hint 3
You can easily insert multiple items in an already sorted stack by just repeatedly performing what's described in Hint #2. However, you'll need to have an already sorted stack. To get an already sorted stack, you'll need to pop all of the elements off the unsorted stack until it's eventually empty, and then you'll need to push all of the items back on the stack, inserting them in their sorted order one at a time.
:::

<br />

:::spoiler Hint 4
If you're thinking about Hint #3 recursively, the steps are the following:
1. Pop an item from the top of the stack, and hold onto it in memory.
2. Sort the rest of the stack. To do so, repeat step #1 until the stack is empty, at which point you've reached the base case since an empty stack is always sorted.
3. Insert the most recently popped off item from step #1 back into the now sorted stack but in its proper sorted position. The first time that you reinsert an item, it'll be inserted in an empty stack.
:::

## Optimal Time & Space Complexity
:::spoiler
O(n^2) time | O(n) space - where n is the length of the stack
:::

## Solutions

### Official

:::spoiler Solution 1
<br />

```javascript=
// O(n^2) time | O(n) space - where n is the length of the stack
function sortStack(stack) {
  if (stack.length === 0) return stack;
  const top = stack.pop();
  sortStack(stack);
  insertInSortedOrder(stack, top);
  return stack;
}
function insertInSortedOrder(stack, value) {
  if (stack.length === 0 || stack[stack.length - 1] <= value) {
    stack.push(value);
    return;
  }
  const top = stack.pop();
  insertInSortedOrder(stack, value);
  stack.push(top);
}
```
:::

<br />

### Everyone's

:::spoiler 東
```javascript=
function sortStack(stack) {
  const last = stack.pop();
  if(last !== undefined) {
    if(stack[stack.length - 1] === undefined) {
    insertToSortedStack(stack, last);
  } else {
    sortStack(stack);
    insertToSortedStack(stack, last);
    }
  }
  return stack;
}

function insertToSortedStack(curStack, num){
  if(curStack[curStack.length - 1] === undefined) {
    curStack.push(num);
    return curStack;
  }
  
  const last = curStack.pop();
  if(last < num) {
    curStack.push(last);
    curStack.push(num);
    return;
  } else {
    insertToSortedStack(curStack, num);
    curStack.push(last);
  }
  return curStack;
}
```

:::

<br>

:::spoiler Hao
```javascript=
const sortStackRecursive = (stack, min, deep) => {
  if (deep > 0) {
    const pop = stack.pop();

    if (pop !== undefined) {
      const [newMin, pending] = pop < min ? [pop, min] : [min, pop];

      const max = sortStackRecursive(stack, newMin, deep - 1);

      const [newMax, consume] = max > pending ? [max, pending] : [pending, max];

      stack.push(consume);

      return newMax;
    }
  }

  return min;
};

const getStackLength = (stack) => {
  const getStatkLengthRecursive = (stack) => {
    const pop = stack.pop();
    let acc = 0;

    if (pop !== undefined) {
      acc = getStatkLengthRecursive(stack) + 1;
      stack.push(pop);
    }

    return acc;
  };

  const length = getStatkLengthRecursive(stack);

  return length;
};

function sortStack(stack) {
  const length = getStackLength(stack);

  for (let i = length; i > 0; i -= 1) {
    sortStackRecursive(stack, Number.POSITIVE_INFINITY, i);
  }

  return stack;
}
```
:::

<br>

:::spoiler YC
```javascript=
/*
  time: O(n^2) - where n is the length of the stack
  space: O(n) - where n is the length of the stack
*/

function sortStack(stack) {
  if(stack.length === 0) return stack;
  const curr = stack.pop();
  sortStack(stack);
  sort(stack, curr);
  return stack;
}

function sort(stack, num){
  if(stack.length === 0 || stack[stack.length - 1] < num){
    stack.push(num); 
    return;
  }
  const top = stack.pop();
  sort(stack, num);
  stack.push(top);
}
```
:::

<br>

:::spoiler 月薪

```javascript=
```
:::

<br>

## Discussion

### Concept

1. Bubble sort
2. Record all the steps you need

![](https://i.imgur.com/t4e2QmS.png)
