Algorithm for sorting a stack

It seems you are prohibited to use any data structures except for stack in training purposes.

You can sort stack using the second stack.

For example - choosing minimal element at every stage.

Pop top element and put it into smin variable.

Pop all oter elements. If current one is smaller than smin, push smin into the second stack and put new value.

After all, push smin into the empty main stack, then move all elements from the second stack into the main one.

Repeat but make n-1 steps (you can remember count when moving elements if your stack has no Count property). Repeat until all elements are sorted (unsorted rest size becomes 1)

Stack is prepopulated you can try popping each element of stack into an array(O(n) auxiliary space ). Sort the array based on your favorite sort algo(There are algo that can work in O(nLog(n))) < o(n*n), checkout heap sort. Push them back into the stack.

Stack is empty Use priority Queue instead :|

If you are able to move the smallest element to the bottom of the stack, you are done (because you can do this repeatedly, shrinking the stack every time).

To move the smallest to the bottom, you move all elements to an auxiliary stack but keep apart the smallest so far. When the main stack is empty, push the smallest then all other elements.

E.g.

4 5 2 7| 

4 5 2| : 7
4 5|7  : 2
4|5 7  : 2
|4 5 7 : 2

2|4 5 7 
2 4|5 7
2 4 5|7
2 4 5 7|

As the challenge mentions "recursive", it looks like you should use the call stack (and stack frames) for preserving data while sorting takes place.

I would suggest a selection-sort kind of algorithm, where the stack has an unsorted, upper part and a sorted lower part. At the start, the unsorted part is the whole stack. Then make n iterations and in each iteration we find the greatest value in the unsorted part and move it to the top of the sorted part.

In more detail, in each iteration we perform the following steps:

• Recursively pop values, and keep track of the greatest value encountered. Remember at each recursive call whether the current value was found to be greater than the greatest value found so far.

• At the bottom of the unsorted part, push that greatest value and stop the recursion. This makes the stack size 1 greater upon exit of the function than it was on entry.

• While exiting the recursive calls, if the current value was the one passed down the recursion as the greatest so far, then check if the stack is still greater than expected:

  • If so, this means that indeed that value turned out to be the all-over maximum, and it should not be pushed unto the stack again, as it was put at the bottom. By not pushing it again, the stack size is now equal upon exit as it was on entry.
  • If not so, this means that a greater value was identified deeper in the recursion tree, and the current value should just be pushed to the stack again.

• If the current value was not the one passed down the recursion as the greatest so far, just push back the value.

After this phase we have moved the greatest value to the bottom of the stack. Now define the "bottom" of the stack as being one entry higher, so to leave the found least value untouched. Repeat the above steps until that new "bottom" is reached.

Keep raising the bottom like that until that bottom matches the top of the stack. This indicates that the stack is completely sorted.

Here is an implementation in JavaScript:

function moveMaxDown(stack, bottom, maxValue) {
    let value = stack.pop();
    let len = stack.length; // Memorize length before recursing
    if (len > bottom) { // Not reached the bottom yet
        if (value <= maxValue) {
            moveMaxDown(stack, bottom, maxValue);
        } else {
            moveMaxDown(stack, bottom, value);
            if (stack.length > len) return; // Current value was already inserted
        }
    } else {
        if (value <= maxValue) stack.push(maxValue); // Extra push
    }
    stack.push(value);
}

function stackSort(stack) {        
    for (let bottom = 0; bottom < stack.length; bottom++) {
        moveMaxDown(stack, bottom, -Infinity);
    }
    return stack;
}

// demo
console.log(stackSort([3, 2, 1]));
console.log(stackSort([11, 2, 32, 3, 41]));