In this article, you will learn how to sort a linked list using the merge sort algorithm. It is one of the efficient sorting algorithms and is based on the divide and conquer approach. Since linked list cannot access elements in O(1) time as arrays do, algorithms, such as quicksort or heap sort, either cannot be applied or are inefficient. So, merge sort is a preferred sorting algorithm.
As already mentioned, merge sort is a divide and conquer algorithm. Therefore, it divides the list recursively into two halves, sorts them, and combines them back to get a single sorted list. Two questions can come to your mind at this point.
Divide the linked list into two halves
First, how do we divide the linked list into two halves? For that, we define a function
findMid(). It takes the head of a linked list and finds the mid using the two-pointer approach. One pointer is slow and takes one step at a time. The second fast pointer, however, takes two steps at a time. Therefore, when the fast pointer reaches the end of the list, the slow pointer will be in the middle. Finally, we return that node.
Now that we know where the middle node is, we divide the linked list into two halves. The left part contains nodes from the head to the middle node. The right half has nodes after the mid to the end.
Merge the two halves
The next question is, how do we merge the two halves? For that, we create a dummy result node. We will add items from the left and right parts in this list in sorted order. Moreover, we add items to the end using a temp pointer that always points to the result list’s end.
Initially, l and r point to the beginning of left and right halves, respectively. If the left node’s value is greater than the value at the right node, we add the left node in the result list and increment the l pointer. Otherwise, we add the right node and increment the r pointer. We continue doing this until one of the parts becomes empty. Then, we add nodes of the other half to the result list. Finally, we return it.
Consider the following image for an illustration of the merge function.
The implementation of the Merge Sort Algorithm on a Linked List is given below.
class Node: def __init__(self, val=None, next=None): self.val = val self.next = next class LinkedList: def __init__(self): self.head = None #appends item to the linked list def add(self, val): new_node = Node(val) if self.head == None: self.head = new_node else: temp = self.head while temp.next: temp = temp.next temp.next = new_node def findMid(head): slow = head fast = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next return slow def merge(l, r): result = Node() #create a dummy node temp = None #node to add items at the end of the result list while l and r: #left node's value is less or equal to than the right node's value if l.val <= r.val: if temp==None: #no nodes in the result list, then add the first value to it result.val = l.val temp = result #update the temp pointer else: temp.next = l #add the new node after the last node in the result list temp = temp.next #update the temp to point to the end l = l.next #left node's value is greater than the right node's value else: if temp==None: result.val = r.val temp = result else: temp.next =r temp = temp.next r = r.next if l == None: #left part has been added to the list, then add the remaining right part temp.next = r if r == None: #right part has been added to the list, then add the remaining left part temp.next = l return result #return the list def mergeSort(head): if head == None: return None if head.next == None: return head mid = findMid(head) #find the mid of the given list left = head right = mid.next mid.next = None l = mergeSort(left) r = mergeSort(right) return merge(l, r) #helper function to traverse a linked list and print its values def traverse(head): temp=head while temp: print(temp.val, end=" ") temp = temp.next print() #create a linked list listt = LinkedList() #add items to the list listt.add(4) listt.add(-10) listt.add(6) listt.add(18) listt.add(0) listt.add(15) print("Before sorting") traverse(listt.head) sorted = mergeSort(listt.head) print("After sorting") traverse(sorted)
4 -10 6 18 0 15
-10 0 4 6 15 18
Consider the following image illustrating the steps to sort a linked list using the merge sort algorithm.