Merge sort for Singly Linked List using Python

 Merge Sort , so merge sort divide linked list into smaller part and sort and merge those parts in one linked list, let's see how?

 First Check out Basic Operation on Singly Linked list. 

Code:

class Node:

def __init__(self, data=None):

self.data = data

self.next = None

class LinkedList:

def __init__(self):

self.head = None

""" Merge Sort"""

# this funtion sort divided linked list and merge

# them into one linked list

def sortedMerge(self,a,b):

result = None

if a is None:

return b

if b is None:

return a

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 h is None or h.next is None:

return h

#find middle

middle = self.getMiddle(h)

# take middle.next in nextToMiddle for dividing

# linked list in two part

nextToMiddle = middle.next

# it divides

middle.next = None

# recursion

left = self.mergeSort(h)

right = self.mergeSort(nextToMiddle)

#it stops when linked list won't divided

#now sort and merge

sortedList = self.sortedMerge(left,right)

return sortedList

# it will find middle of linked list

def getMiddle(self,head):

if head is None:

return head

slow = head

fast = head

while fast.next and fast.next.next:

slow = slow.next

fast = fast.next.next

return slow

 Time Complexity:

• Best: 𝛺(n*log n)
• Average:Θ(n*log n)
• Worst: O(n*log n)

 Space Complexity: O(log n)

Note: if You have any suggestion put in comments.

Thank You 😊😊

Other Sorting Algorithms:

• Bubble Sort for Singly Linked list
• Insertion Sort for Singly Linked list
• Quick Sort for Singly Linked list