Sort a stack in 2n space

Question

I've been able to find several implementations of this problem in Java and C, but I haven't been able to find an example that uses JavaScript. It is a fairly common technical interview question:

Sort a stack in 2n space. (Sort a stack using only 2 stacks)

Possible duplicate of [sorting elements of stack using javascript](https://stackoverflow.com/questions/41283590/sorting-elements-of-stack-using-javascript) — Hodrobond, May 22 '17 at 15:53
You can sort a stack in JS *in-place* as the stack would be implemented as random access array without additional space requirements... could you clarify? If it's an interview question and you are only allowed to use push and pop, then it's a different matter of course. — le_m, May 22 '17 at 15:54
@dalyhabit so you mean you will have 3 stacks in total right, like one stack as input and we are allowed to use two extra stacks right ? — zenwraight, May 22 '17 at 15:57

score 0 · Answer 1 · answered May 22 '17 at 17:57

We can implement a simple, non-recursive bubble-sort given a stack and a temporary buffer:

Iteratively pop two elements from the stack, swap these two elements if the first one is bigger, then push them back on a buffer.
Repeat step 1. but reverse the direction, so all elements from the buffer will end up back on the stack.

Repeat step 1. and 2. until no more elements need to be swapped.

function bubble(stack, buffer, up = true) {
  let swaps = 0;
  let last = stack.pop();
  while (stack.length > 0) {
    let next = stack.pop();
    if (up ? last > next : last < next) swaps++;
    else [next, last] = [last, next];
    buffer.push(next);
  }
  buffer.push(last);
  return swaps;
}

function sort(stack, up = true, buffer = []) {
  do bubble(stack, buffer, !up);
  while (bubble(buffer, stack, up) > 0);
  return stack;
}

// Example:
console.log(sort([6,3,9,3,2,8])); // [2, 3, 3, 6, 8, 9]

For a recursive solution, see https://stackoverflow.com/a/41293937/1647737

Sort a stack in 2n space

1 Answers1