🔗 Merge Sort for Linked List (Step-by-Step Guide)

Sorting a linked list efficiently is an important problem in data structures.
Unlike arrays, linked lists do not support random access, so Merge Sort is the best choice.

📌 Problem Statement

Given the head of a linked list, sort it using Merge Sort and return the sorted list.

🔍 Examples

Example 1:
Input: 10 → 30 → 20 → 50 → 40 → 60
Output: 10 → 20 → 30 → 40 → 50 → 60

Example 2:
Input: 9 → 5 → 2 → 8
Output: 2 → 5 → 8 → 9

🧠 Intuition

Merge Sort works by:

Dividing the list into halves
Sorting each half recursively
Merging the sorted halves

👉 This works efficiently for linked lists because merging is easy using pointers.

🔄 Approach (Merge Sort)

Step-by-Step:

Find the middle of the list
Split the list into two halves
Recursively sort both halves
Merge the sorted lists

💻 Python Code

class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

def get_middle(head):
slow = head
fast = head.next

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

return slow

def merge(l1, l2):
dummy = ListNode()
tail = dummy

while l1 and l2:
    if l1.val <= l2.val:
        tail.next = l1
        l1 = l1.next
    else:
        tail.next = l2
        l2 = l2.next

    tail = tail.next

tail.next = l1 if l1 else l2
return dummy.next

def merge_sort(head):
if not head or not head.next:
return head

# Step 1: find middle
mid = get_middle(head)
right_head = mid.next
mid.next = None

# Step 2: recursive sort
left = merge_sort(head)
right = merge_sort(right_head)

# Step 3: merge
return merge(left, right)

🧾 Dry Run

For:
10 → 30 → 20 → 50

Step-by-step:

Split → [10 → 30] and [20 → 50]
Split further → [10], [30], [20], [50]
Merge → [10 → 30], [20 → 50]
Final merge → [10 → 20 → 30 → 50]

⚡ Complexity

Time Complexity: O(n log n)
Space Complexity: O(log n) (recursion stack)

🔥 Why Merge Sort for Linked List?

No random access needed
Efficient merging using pointers
Better than QuickSort for linked lists

⚠️ Edge Cases

Empty list
Single node
Already sorted list

🏁 Conclusion

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