# Implement Merge Sort Algorithm on Linked List

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

def __init__(self):

#appends item to the linked list
new_node = Node(val)

else:
while temp.next:
temp = temp.next
temp.next = new_node

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

return None

mid = findMid(head) #find the mid of the given list
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
while temp:
print(temp.val, end=" ")
temp = temp.next
print()

print("Before sorting")

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.

Back to: Data Structure > Data Structure - Linked List