Merge-sort for Stacks

Question

Any idea why my Stack merge-sort isn't working? It's pretty identical to my merge-sort for arrays, yet that one works. Is my recursion setup wrong?

Thanks!

def sort(stack):
    if len(stack) > 1:
        middle = len(stack) // 2
        stack_len = len(stack)
        left = Stack()
        right = Stack()
        for i in range(middle):
            left.push(stack.pop())
        for i in range(middle, stack_len):
            right.push(stack.pop())
        sort(left)
        sort(right)
        while(not left.is_empty() and not right.is_empty()):
            if (left.top() < right.top()):
                stack.push(right.pop())
            else:
                stack.push(left.pop())
        while(not left.is_empty()):
            stack.push(left.pop())
        while(not right.is_empty()):
            stack.push(right.pop())

Here is my Stack ADT implementation:

class Stack:

    def __init__(self):
        self._data = []

    def __len__(self):
        return len(self._data)

    def is_empty(self):
        return len(self) == 0

    def push(self, i):
        self._data.append(i)

    def pop(self):
        if not self.is_empty():
           return self._data.pop()
        raise IndexError('Cannot pop an empty Stack.')

    def top(self):
        if not self.is_empty():
            return self._data[len(self) - 1]
        raise IndexError('Cannot check the top of an empty Stack.')

My test case is:

if __name__ == '__main__':
    s = Stack()
    s.push(8)
    s.push(0)
    s.push(-4)
    s.push(11)
    s.push(19)
    s.push(21)
    s.push(3)
    s.push(14)
    s.push(1)
    s.push(14)
    print(s._data)
    sort(s)
    print(s._data)

which gives:

[8, 0, -4, 11, 19, 21, 3, 14, 1, 14]

[19, 14, 1, 21, 3, 14, -4, 8, 0, 11]

Answer 1

I assume you are doing this to learn merge sort or LIFO, but if not, since your stack is just a python list (array), the functions sorted(s._data) or s._data.sort() both accomplish what you need. If you need to continue with stack then...

First, debug:

If you want to learn your error, you can place some print() statements to view what your stack looks like at each phase of your code. Your sort function is good, and does separate your arrays properly. The flaw is in the merge section. The merge section of your algorithm occurs after your recursive calls to sort() in the section with the 3 while loops. With your example input, eventually, these arrays will be merged:

MERGING
L [19]
R [11, -4]

Since you are doing this with a stack LIFO, using pop() based on this conditional: left.top() < right.top(), the resultant new stack array becomes: [19, -4, 11]. Last in, First, out, means -4 is added second once the Left array is empty, since Right is emptied. However, with a proper merge, this array would be merged sorted, and should be merged like this:

[-4, 11, 19]

Your next merge is this:

MERGING
L [8, 0]
R [19, -4, 11]

Which results in the new stack being: [11, 0, 8, -4, 19], which eventually leads to 19 being added first to your final stack, thus 19 is in the place of index 0 in your results, and you get this: [19, 14, 1, 21, 3, 14, -4, 8, 0, 11]

Resolution:

To resolve this, you should use a queue instead, which would be FIFO, and you would always add the lowest number first to your queue, which would be at index 0 of your array (i.e. moving from left to right). If you absolutely must use a stack and continue with the append and .pop() methodology, then, I suggest:

First, in the merge section, merge the lesser number with higher precedence over the higher number. Then, before you add from either the Left or Right arrays to the stack in the merging section, you need to ensure that the number you are adding is greater than the current head (Last in) of the stack. If it is not greater, then you need to pop() the stack into a new array or the left / right array (whichever array you are not working on) until the next added value is actually greater than the head of the stack. Then, continue with the same method only adding values to the stack that are greater than the head of the stack, remembering to add the pop'd values back to the stack also in proper order.

Code updated solution

Here is the added code as a solution maintaining the stack methodology:

while(not left.is_empty() and not right.is_empty()):
    if (left.top() > right.top()):
        if stack.is_empty() or stack.top() <= right.top():
            stack.push(right.pop())
        else:
            left.push(stack.pop())
    else:
        if stack.is_empty() or stack.top() <= left.top():
            stack.push(left.pop())
        else:
            right.push(stack.pop())
while(not left.is_empty()):
    if stack.is_empty() or stack.top() <= left.top():
        stack.push(left.pop())
    else:
        right.push(stack.pop())
while(not right.is_empty()):
    if stack.is_empty() or stack.top() <= right.top():
        stack.push(right.pop())
    else:
        left.push(stack.pop())
while(not left.is_empty()):
    stack.push(left.pop())

Solution with updates: [-4, 0, 1, 3, 8, 11, 14, 14, 19, 21]