Merge Sort on Linked List

Question

Merge Sort functions with only some inputs when run on a linked list. If I include 0 in the list of inputs, only 0 is returned from the final print() call. I don't know what I'm doing wrong

class StackNode(object):
    def __init__(self, data):
        self.data = data
        self.prev = None

class Stack(object):
    def __init__(self):
        self.head = None
        self.count = 0

    def push(self, data):
        if (self.head == None):
            self.head = StackNode(data)
            self.count += 1
            return
        node = StackNode(data)
        node.prev = self.head
        self.head = node
        self.count += 1
        return

    def pop(self):
        node = self.head
        self.head = self.head.prev
        self.count -= 1
        return node

    def print(self):
        node = self.head
        if(node == None):
            return
        print(node.data)
        while(node.prev):
            node = node.prev
            print(node.data)

    def MergeSort(self, h):
        if h == None or h.prev == None:
            return h
        middle = self.GetMiddle(h)
        nextToMiddle = middle.prev
        middle.prev = None
        left = self.MergeSort(h)
        right = self.MergeSort(nextToMiddle)
        sortedList = self.SortedMerge(left, right)
        return sortedList


     def SortedMerge(self, a, b):
        if a is None:
            return b
        if b is None:
            return a
        if(a.data > b.data):
            result = a
            a.prev = self.SortedMerge(a.prev, b)
        else:
            result = b
            b.prev = self.SortedMerge(b.prev, a)
        return result

    def GetMiddle(self, head):
        if head == None:
            return head
        slow = head
        fast = head
        while(fast.prev != None and fast.prev.prev != None):
            slow = slow.prev
            fast = fast.prev.prev
        return slow

a = Stack()
a.push(2)
a.push(5)
a.push(1)
a.push(4)
a.push(3)
a.push(7)
a.print()
a.MergeSort(a.head)
print("after: ")
a.print()

I transcribed my code directly from the linked list merge sort example given on geeksforgeeks.com, with the only difference being that my code creates a stack instead of a queue

Answer 1

MergeSort returns the head of a sorted list, so the call in the main code should be:

a.head = a.MergeSort(a.head)

For a sorted stack, it would seem that the result of doing successive list.pop() should return the nodes in data order, but the code is using ">" instead of "<=" in the compare, reversing the order.

---

Python 2.7 complained about using the name print for the class print function, and also complained about the 5 (instead of 4) spaces before "def SortedMerge(self, a, b):"

---

SortedMerge() does one level of recursion for every node merged. For a large list, the program will get stack overflow. Since the list class includes a count, the code could use list.count//2 to determine the number of nodes to advance to reach the midpoint, then use (count//2) for the size of the left half and (count-(count//2)) for the size of the right half. A bottom up merge sort is faster still. However, with python, the overhead of interpreting code is so large that I don't know if it will make a difference. Here is a link to both top down and bottom up merge sort for a linked list, in java, that use a common merge function:

Merge Sort for Singly Linked List seems to remove any numbers larger than the final number I input into the list

---

I converted the code to python. The merge function is the same for both examples. Note the sort logic is the same, only the push and pop functions result in the linked list acting as a stack. Merge function:

    def Merge(self, a, b):
        if a is None:
            return b
        if b is None:
            return a
        r = StackNode(0)                    # dummy node
        d = r
        while(True):
            if(a.data <= b.data):
                d.prev = a
                d = a
                a = a.prev
                if(a == None):
                    d.prev = b
                    break
            else:
                d.prev = b
                d = b
                b = b.prev
                if(b == None):
                    d.prev = a
                    break
        return r.prev

Top down example:

    def MergeSort(self):
        if(self.count < 2):
            return
        self.head = self.MergeSortR(self.head, self.count)

    def MergeSortR(self, h, n):
        if(n < 2):
            return h
        n2 = n//2
        t = self.Scan(h, n2-1)
        m = t.prev
        t.prev = None
        h = self.MergeSortR(h, n2)
        m = self.MergeSortR(m, n-n2)
        h = self.Merge(h, m)
        return h

    def Scan(self, h, n):
        while(n > 0):
            h = h.prev
            n = n-1
        return h

Bottom up example:

    def MergeSort(self):
        if(self.count < 2):
            return
        an = [None] * 32
        node = self.head
        while(node != None):
            prev = node.prev
            node.prev = None
            i = 0
            while((i < 32) and (an[i] != None)):
                node = self.Merge(an[i], node)
                an[i] = None
                i = i+1
            if(i == 32):
                i = i-1
            an[i] = node
            node = prev
        for i in xrange (0, 32):
            node = self.Merge(an[i], node)
        self.head = node

Test code for 512K nodes. On my system, top down takes about 4.5 seconds, bottom up about 3.9 seconds. To get an idea of the overhead of Python, bottom up in C takes about 0.06 seconds.

import random
from time import time
p = [random.randint(0, 2147483647) for r in xrange(512*1024)]
a = Stack()
for i in xrange (0, len(p)):
    a.push(p[i])
s = time()
a.MergeSort()
e = time()
print e - s
for i in xrange (0, len(p)):
    p[i] = a.pop().data
for i in xrange (1, len(p)):
    if(p[i-1] > p[i]):
        print("error")
        break