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

By | November 12, 2013

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 n 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;
}
```

## 3 thoughts on “Sort a stack in ascending order in O(n log n)”

1. Manik Saini

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.

2. Dinozi

there is some problem in static class

3. rcgldr

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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.