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.

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.

Implementation

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)

Output

Before sorting

4 -10 6 18 0 15

After sorting

-10 0 4 6 15 18

Consider the following image illustrating the steps to sort a linked list using the merge sort algorithm.