Merge Sort for Linked List

Merge Sort for Linked List
Problem Statement

We are given the head of a linked list, and we need to sort the linked list using Merge Sort.

Merge Sort is very efficient for linked lists because:

Linked lists do not support random access
Merge sort does not require shifting elements
Works efficiently with pointers
Why Merge Sort for Linked List?

Sorting algorithms like:

Bubble Sort
Selection Sort
Insertion Sort

are O(n²).

But Merge Sort = O(n log n), which is much faster for large lists.

Merge Sort Idea for Linked List

Merge Sort follows Divide and Conquer:

Steps:
Find the middle of the linked list
Split the list into two halves
Recursively sort both halves
Merge the sorted halves

Algorithm Steps
Step 1 – Find Middle of Linked List

Use slow and fast pointer

Slow moves 1 step
Fast moves 2 steps
When fast reaches end, slow is at middle
Step 2 – Split the List

Break the list into two halves

Step 3 – Sort Both Halves Recursively
Step 4 – Merge Two Sorted Lists

Python Implementation
class Node:
def init(self, data):
self.data = data
self.next = None

def getMiddle(head):
if head is None:
return head

slow = head
fast = head.next

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

return slow

def merge(left, right):
if left is None:
return right
if right is None:
return left

if left.data <= right.data:
    result = left
    result.next = merge(left.next, right)
else:
    result = right
    result.next = merge(left, right.next)

return result

def mergeSort(head):
if head is None or head.next is None:
return head

middle = getMiddle(head)
next_to_middle = middle.next
middle.next = None

left = mergeSort(head)
right = mergeSort(next_to_middle)

sorted_list = merge(left, right)
return sorted_list

def printList(head):
temp = head
while temp:
print(temp.data, end=" -> ")
temp = temp.next
print("None")

Create Linked List

head = Node(50)
head.next = Node(20)
head.next.next = Node(40)
head.next.next.next = Node(10)
head.next.next.next.next = Node(30)

head = mergeSort(head)
printList(head)
Example
Input Linked List
50 -> 20 -> 40 -> 10 -> 30
Splitting
50 -> 20 -> 40
10 -> 30
After Sorting
10 -> 20 -> 30 -> 40 -> 50

Complexity Analysis
Type Complexity
Time O(n log n)
Space O(log n) recursion

Merge Sort Steps Summary
Step Operation
Find middle Slow & Fast pointer
Split list Break into halves
Sort halves Recursion
Merge lists Merge sorted lists

Conclusion
Merge Sort is the best sorting algorithm for linked lists because:

No random access needed
Efficient merging using pointers
Time complexity O(n log n)
Works well for large linked lists