Is it possible to sort a stack using merge sort?

algorithm, sorting

Solution

Yes, we can. The trick is understanding that when the stack is sorted, the head is the largest element - and we want to iterate it from lower to higher We can reverse a stack however in O(n).

reverse(stack):
   s <- new stack
   while stack.isEmpty() == false:
       s.push(stack.pop)
   return s

Now, using it, and assuming you can use size() as well, it is fairly easy to implement and is a standard for most stack implementation - we can implement a merge sort:

Pseudo code:

mergeSort(stack):
   if stack.isEmpty():
       return stack
   s1 <- new stack
   s2 <- new stack
   //   O(n):
   while s1.size() < stack.size():
        s1.push(stack.pop())
   while (stack.isEmpty() == false):
        s2.push(stack.pop())           
   mergeSort(s1) //half the size of stack
   mergeSort(s2) //half the size of stack
   //head of s1 and s2 is the largest element
   s1 <- s1.reverse() //easily implemented in O(n)
   s2 <- s2.reverse()
   //now head of s1 and s2 is the smallest element
   while (s1.isEmpty() == false and s2.isEmpty() == false):
        if (s1.peek() < s2.peek()):
            stack.push(s1.pop())
         else:
            stack.push(s2.pop())
   //the 'tail' of one stack:
   while (s1.isEmpty() == false):
         stack.push(s1.pop())
   while (s2.isEmpty() == false):
         stack.push(s2.pop())
   //head is the largest, stacks are sorted
   return stack

Correctness: Base: The stop clause is an empty stack, which is sorted. Hypothesis: s1 and s2 are sorted. Step: After reversing, s1 and s2 are basically traversed in the order of lower->higher, in sorted area when taking off elements using the pop() method. Since we always insert the smaller element from each stack, and we are traversing each stack from low to high - we get that the resulting stack is in order.

Complexity: Excluding recursive calls, each step is `O(stack.size()) = O(n)`. This is the same behavior as regular merge sort, and the rest of the complexity follows the same steps of original merge sort to get `O(nlogn)`.

Problem

A stack can be implemented as a linked list. Linked lists can be sorted using merge sort: O(n log n) time O(n) space It makes sense to be able to sort a stack using merge sort. If that's the case, what would the code look like? (after a quick search on the web, I only found brute force algorithms O(n^2))

Original source