Tag Archives: stack

Sort a stack in ascending order in O(n log n)

Another FAQ on the programming interview.

Question

Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.

Solution

Cracking the Coding Interview (4ed) (see page 121) provided an O(N^2) algorithm by using one more stack. The idea is to pull an item from the original stack and push it on the other stack. If pushing this item would violate the sort order of the new stack, the algorithm removes enough items from it so that it’s possible to push the new item. Because of the copyright, I won’t paste her code here, but you can easily find it out online (:P).

Can we do better? I think we can mimic the way of quicksort by picking a pivot from the stack (using pop) first. Then we conduct the partition operation by pushing all elements in the stack with values less than the pivot into one stack, while all elements with values greater than the pivot into the other. After that, we recursively sort two sub-stacks and merge two at last with the pivot in the middle.

Because we can only use the stack structure, I pick the pivot using pop. The merge operation is tricky and I am not sure if we can have a better way to combine two stacks. So if you have any idea, please let me know.

On average, this algorithm makes O(n log n) comparisons to sort items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.

public static Stack<Integer> sort(Stack<Integer> s) {
  if (s.isEmpty()) {
    return s;
  }
  int pivot = s.pop();
  
  // partition
  Stack<Integer> left  = new Stack<Integer>();
  Stack<Integer> right = new Stack<Integer>();
  while(!s.isEmpty()) {
    int y = s.pop();
    if (y < pivot) {
      left.push(y);
    } else {
      right.push(y);
    }
  }
  sort(left);
  sort(right);
   
  // merge
  Stack<Integer> tmp = new Stack<Integer>();
  while(!right.isEmpty()) {
    tmp.push(right.pop());
  }
  tmp.push(pivot);
  while(!left.isEmpty()) {
    tmp.push(left.pop());
  }
  while(!tmp.isEmpty()) {
    s.push(tmp.pop());
  }
  return s;
}

read more