Merge Sort for Linked List

Merge Sort is one of the most efficient sorting algorithms for linked lists. Unlike arrays, linked lists do not support random access, making algorithms like Quick Sort less efficient. Merge Sort, however, works exceptionally well because it uses the divide‑and‑conquer approach and requires only O(1) extra space (excluding recursion stack) when implemented iteratively.

Why Merge Sort for Linked Lists?

• Linked list nodes can be split and merged without copying elements.
• No need for extra array storage (unlike array‑based merge sort).
• Worst‑case time complexity is O(n log n).
• It is a stable sort.

Algorithm Steps

1. Find the middle of the linked list using the slow‑fast pointer technique.
2. Split the list into two halves at the middle.
3. Recursively sort the left and right halves.
4. Merge the two sorted halves into one sorted list.

Helper Functions

Find Middle Node

def find_middle(head):
    if head is None:
        return None
    slow = head
    fast = head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Merge Two Sorted Lists

def merge(left, right):
    dummy = Node(0)
    tail = dummy
    while left and right:
        if left.val <= right.val:
            tail.next = left
            left = left.next
        else:
            tail.next = right
            right = right.next
        tail = tail.next
    tail.next = left or right
    return dummy.next

Merge Sort Implementation

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

    mid = find_middle(head)
    right_head = mid.next
    mid.next = None  # Split the list

    left_sorted = merge_sort(head)
    right_sorted = merge_sort(right_head)

    return merge(left_sorted, right_sorted)

Complete Example

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def create_list(arr):
    head = Node(arr[0])
    curr = head
    for v in arr[1:]:
        curr.next = Node(v)
        curr = curr.next
    return head

def print_list(head):
    vals = []
    while head:
        vals.append(str(head.val))
        head = head.next
    print(" -> ".join(vals))

# Test
head = create_list([4, 2, 1, 3, 5])
sorted_head = merge_sort(head)
print_list(sorted_head)  # Output: 1 -> 2 -> 3 -> 4 -> 5

Complexity

Applications

• Sorting linked lists in libraries and frameworks.
• External sorting where data is stored as linked structures.
• Base for more complex operations like merge‑sort‑based union/intersection of sorted lists.