Merge Sort on Linked Lists — Pointer Surgery

Merge sort on linked lists keeps the O(n log n) divide-and-conquer structure but avoids O(n) auxiliary arrays by rewiring next pointers. It is the classic interview bridge between pointer juggling and recursion.

Why this shows up in the real world

Big data frameworks sometimes merge sorted linked runs in memory-constrained workers where array resizing is painful. Audio buffer chains in low-latency pipelines are naturally linked; merging two sorted chains without copying reduces cache misses. Even if you implement on arrays in contests, the linked version teaches in-place merge thinking.

Core idea (explained for students)

Use slow/fast pointers to find the middle and split into two lists. Recursively sort each half. Merge sorted lists with a dummy head and two iterators, choosing the smaller head each step—O(n) per level. Depth is log n; total O(n log n). Watch stack depth on very long lists—iterative bottom-up merge exists for advanced readers.

Try this in Python

# Conceptual sketch — Node class omitted; focus on merge pattern
def merge_two_sorted(h1, h2):
    dummy = cur = {"next": None}
    while h1 and h2:
        if h1["val"] <= h2["val"]:
            cur["next"], h1 = h1, h1["next"]
        else:
            cur["next"], h2 = h2, h2["next"]
        cur = cur["next"]
    cur["next"] = h1 or h2
    return dummy["next"]


print("merge_two_sorted is the heart of linked-list merge sort")

Common mistakes

• Losing nodes when splicing—draw before coding.
• Incorrect slow/fast termination on even vs odd lengths.
• Forgetting to detach the first half’s tail from the second half before sorting.

Key takeaways

• Pointer merge avoids extra array but not extra stack unless iterative.
• Same asymptotics as array merge sort.
• Great practice for dummy node pattern.