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

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:

40 -> 20 -> 60 -> 10

Split:

• [40 -> 20]
• [60 -> 10]

Sort:

• [20 -> 40]
• [10 -> 60]

Merge:

10 -> 20 -> 40 -> 60

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.