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 *push*ing 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 *n* items. In the worst case, it makes *O(n ^{2})* 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; }

The stack sort can be done in (n logn) by using more stacks. But if you have constraint on the memory usage as specified in “Cracking the coding interview” at most only one stack is to be used. So sorting will take place in O(n^2) time.

there is some problem in static class

With 3 stacks, a polyphase merge sort is fastest, but the code is complex. There’s an initial distribution based on element count versus the highest Fibonacci number <= element count. Merging of runs alternates between ascending and descending, and the element count determines if the initial merge is ascending or descending. The code also needs to keep track of run sizes that can vary during a merge pass.