Is it possible to sort a stack using merge sort?

Question

The 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 the stack using merge sort.

If so, what does the code look like?

(after a quick search on the Internet, I found only brute force algorithms O (n ^ 2))

Answer 1

Yes we can. The trick is to understand that when sorting a stack, the head is the largest element - and we want to iterate over it from lower to higher. We can flip the stack, but in O (n).

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

, , size(), - :

:

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

:
: stop - , .
: s1 s2 . : s1 s2 → , pop(). , - , .

:
, O(stack.size()) = O(n). , , , O(nlogn).

Answer 2

, , :

void mergesortStack(Stack input) {
    if (input.isEmpty()) {
        return;
    }

    Stack stackLeft = new Stack();
    Stack stackRight = new Stack();

    // split
    while (!input.isEmpty()) {
        stackLeft.push(input.pop());
        if (!input.isEmpty()) {
            stackRight.push(input.pop());
        }
    }

    // recurse
    if (!stackLeft.isEmpty() && !stackRight.isEmpty()) {
        mergesortStack(stackLeft);
        mergesortStack(stackRight);
    }

    // merge
    Stack tmpStack = new Stack();
    while (!stackLeft.isEmpty() || !stackRight.isEmpty()) {
        if (stackLeft.isEmpty()) {
            tmpStack.push(stackRight.pop());
        } else if (stackRight.isEmpty()) {
            tmpStack.push(stackLeft.pop());
            // set an appropriate compare method
        } else if (stackLeft.peek().compareTo(stackRight.peek()) >= 0) {
            tmpStack.push(stackLeft.pop());
        } else {
            tmpStack.push(stackRight.pop());
        }
    }

    // reverse stack
    while (!tmpStack.isEmpty()) {
        input.push(tmpStack.pop());
    }
}