Merge Sort for Linked List Python

PROGRAM TO MERGE SORT FOR LINKED LISTS

# create Node using class Node.

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

    def __init__(self):

        self.head = None

      

    # push new value to linked list

    # using append method

    def append(self, new_value):

          

        # Allocate new node

        new_node = Node(new_value)

          

        # if head is None, initialize it to new node

        if self.head is None:

            self.head = new_node

            return

        curr_node = self.head

        while curr_node.next is not None:

            curr_node = curr_node.next

              

        # Append the new node at the end

        # of the linked list

        curr_node.next = new_node

          

    def sortedMerge(self, a, b):

        result = None

          

        # Base cases

        if a == None:

            return b

        if b == None:

            return a

              

        # pick either a or b and recur..

        if a.data <= b.data:

            result = a

            result.next = self.sortedMerge(a.next,b)

        else:

            result = b

            result.next = self.sortedMerge(a, b.next)

        return result

      

    def mergeSort(self, h):

          

        # Base case if head is None

        if h == None or h.next == None:

            return h

  

        # get the middle of the list 

        middle = self.getMiddle(h)

        nexttomiddle = middle.next

  

        # set the next of middle node to None

        middle.next = None

  

        # Apply mergeSort on left list 

        left = self.mergeSort(h)

          

        # Apply mergeSort on right list

        right = self.mergeSort(nexttomiddle)

  

        # Merge the left and right lists 

        sortedlist = self.sortedMerge(left, right)

        return sortedlist

      

    # Utility function to get the middle 

    # of the linked list 

    def getMiddle(self, head):

        if (head == None):

            return head

  

        slow = head

        fast = head

  

        while (fast.next != None and 

               fast.next.next != None):

            slow = slow.next

            fast = fast.next.next

              

        return slow

          

# Utility function to print the linked list 

def printList(head):

    if head is None:

        print(' ')

        return

    curr_node = head

    while curr_node:

        print(curr_node.data, end = " ")

        curr_node = curr_node.next

    print(' ')

      

# Driver Code

if __name__ == '__main__':

    li = LinkedList()

      

    # Let us create a unsorted linked list

    # to test the functions created. 

    # The list shall be a: 2->3->20->5->10->15 

    li.append(15)

    li.append(10)

    li.append(5)

    li.append(20)

    li.append(3)

    li.append(2)

      

    # Apply merge Sort 

    li.head = li.mergeSort(li.head)

    print ("Sorted Linked List is:")

    printList(li.head)




OUTPUT

Sorted Linked List is: 
2 3 5 10 15 20

CREDITS: https://www.geeksforgeeks.org/merge-sort-for-linked-list/