Python implementation of Mergesort for Linked list doesn't work
<p>I couldn't find a simple implementation of <code>Merge Sort</code> in Python for <code>Linked Lists</code> anywhere. Here's what I tried:</p>

<h3>Definition for singly-linked list:</h3>

<pre><code>class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None 
</code></pre>

<h3>Merge Sort Implementation:</h3>

<pre><code>def mergeSortLinkedList(A):
    # Base case length of 0 or 1:
    if A == None or A.next == None:
        return A

    leftHalf, rightHalf = splitTheList(A)

    mergeSortLinkedList(leftHalf)
    mergeSortLinkedList(rightHalf)

    # The above two lines should be modified to the following. Thanks to the answers.

    # leftHalf  = mergeSortLinkedList(leftHalf)
    # rightHalf = mergeSortLinkedList(rightHalf)

    return mergeTheLists(leftHalf, rightHalf)
</code></pre>

<p>Split:</p>

<pre><code>def splitTheList(sourceList):
    if sourceList == None or sourceList.next == None:
        leftHalf = sourceList
        rightHalf = None

        return leftHalf, rightHalf

    else:
        midPointer = sourceList
        frontRunner = sourceList.next
        # totalLength += 1        - This is unnecessary

        while frontRunner != None:
            frontRunner = frontRunner.next

            if frontRunner != None:
                frontRunner = frontRunner.next
                midPointer = midPointer.next

    leftHalf = sourceList
    rightHalf = midPointer.next
    midPointer.next = None

    return leftHalf, rightHalf
</code></pre>

<p>Merge:</p>

<pre><code>def mergeTheLists(leftHalf, rightHalf):
    fake_head = ListNode(None)
    curr = fake_head

    while leftHalf and rightHalf:
        if leftHalf.val &lt; rightHalf.val:
            curr.next = leftHalf
            leftHalf = leftHalf.next

        else:
            curr.next = rightHalf
            rightHalf = rightHalf.next

        curr = curr.next

    if leftHalf == None:
        curr.next = rightHalf

    elif rightHalf == None:
        curr.next = leftHalf

    return fake_head.next
</code></pre>

<h3>Data:</h3>

<pre><code># Node A:
nodeA1 = ListNode(2)

nodeA2 = ListNode(1)
nodeA1.next = nodeA2

nodeA3 = ListNode(9)
nodeA2.next = nodeA3

nodeA4 = ListNode(3)
nodeA3.next = nodeA4

# Node C:
nodeC1 = ListNode(5)
nodeA4.next = nodeC1

nodeC2 = ListNode(6)
nodeC1.next = nodeC2

nodeC3 = ListNode(4)
nodeC2.next = nodeC3

nodeC4 = ListNode(5)
nodeC3.next = nodeC4
</code></pre>

<p>Expected output when <code>mergeSortLinkedList(nodeA1)</code> is called:</p>

<pre><code>1 2 3 4 5 5 6 9
</code></pre>

<p>I get the following instead:</p>

<pre><code>2 5 6 9
</code></pre>

<p>I am unable to figure out where the miss is. Please help.</p>

<p>Try changing the lines in the mergeSort function to:</p>

<pre><code>leftHalf = mergeSortLinkedList(leftHalf)
rightHalf = mergeSortLinkedList(rightHalf)
</code></pre>

python algorithm sorting linked-list mergesort