Merge Sort for Linked List

Introduction

Sorting a linked list efficiently is an important problem in data structures. Unlike arrays, we cannot use indexing, so we need a different approach.

The best way to sort a linked list is using Merge Sort, because:

• It works efficiently with linked lists
• It does not require random access

---

Problem Statement

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

---

Example

Input:

40 → 20 → 60 → 10 → 50 → 30

Output:

10 → 20 → 30 → 40 → 50 → 60

---

Why Merge Sort for Linked List?

• Quick Sort is not efficient due to pointer operations

• Merge Sort:

  • Divides list into halves
  • Merges sorted halves efficiently
  • Works in O(n log n) time

---

Key Idea

Merge Sort works in three steps:

1. Find the middle of the list
2. Divide into two halves
3. Merge the sorted halves

---

Step 1: Find Middle of Linked List

We use:

• Slow pointer (moves 1 step)
• Fast pointer (moves 2 steps)

---

Step 2: Merge Two Sorted Lists

Compare nodes and build a sorted list.

---

Python Implementation

```python id="7p2q4z"
class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

def merge(l1, l2):
dummy = ListNode(0)
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 get_middle(head):
slow = head
fast = head.next

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

return slow

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

mid = get_middle(head)
right = mid.next
mid.next = None  # split list

left_sorted = merge_sort(head)
right_sorted = merge_sort(right)

return merge(left_sorted, right_sorted)

---

## Step-by-Step Explanation

For:



```id="w8z2kl"
40 → 20 → 60 → 10

Split:

• [40 → 20]
• [60 → 10]

Sort:

• [20 → 40]
• [10 → 60]

Merge:

10 → 20 → 40 → 60

---

Time and Space Complexity

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

---

Key Points

• Best sorting algorithm for linked lists
• Uses divide and conquer
• Efficient merging using pointers
• Common interview question

---

Conclusion

Merge Sort is the most efficient way to sort a linked list. By dividing the list and merging sorted parts, we achieve optimal performance without extra space for arrays.

Mastering this problem will strengthen your understanding of recursion and linked list manipulation.