Sort a Linked List Using Merge Sort in DSA Python

Mental Model

Split the list into halves, sort each half, then merge them back in order.

Analogy: Imagine sorting a deck of cards by splitting it into smaller piles, sorting each pile, then carefully combining them into one sorted deck.

head -> 4 -> 2 -> 1 -> 3 -> null

Dry Run Walkthrough

Input: list: 4 -> 2 -> 1 -> 3 -> null

Goal: Sort the linked list in ascending order using merge sort

Step 1: Find middle to split list into two halves

4 -> 2 -> null and 1 -> 3 -> null

Why: Splitting helps break down the problem into smaller parts

Step 2: Recursively sort left half (4 -> 2 -> null)

2 -> 4 -> null

Why: Sorting smaller parts makes merging easier

Step 3: Recursively sort right half (1 -> 3 -> null)

1 -> 3 -> null

Why: Right half is already sorted or will be sorted similarly

Step 4: Merge sorted halves (2 -> 4 -> null) and (1 -> 3 -> null)

1 -> 2 -> 3 -> 4 -> null

Why: Merging combines sorted lists into one sorted list

Result:

1 -> 2 -> 3 -> 4 -> null

Annotated Code

DSA Python

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

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

    # Find middle of the list
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    mid = slow.next
    slow.next = None  # Split the list into two halves

    left = merge_sort(head)  # Sort left half
    right = merge_sort(mid)  # Sort right half

    return merge(left, right)  # Merge sorted halves

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 print_list(head):
    curr = head
    result = []
    while curr:
        result.append(str(curr.val))
        curr = curr.next
    print(" -> ".join(result) + " -> null")

# Driver code
head = ListNode(4, ListNode(2, ListNode(1, ListNode(3))))
sorted_head = merge_sort(head)
print_list(sorted_head)

if not head or not head.next:

base case: list with 0 or 1 node is already sorted

slow, fast = head, head.next

initialize pointers to find middle node

while fast and fast.next:

advance slow by 1 and fast by 2 to find middle

mid = slow.next slow.next = None

split list into two halves at middle

left = merge_sort(head) right = merge_sort(mid)

recursively sort left and right halves

return merge(left, right)

merge two sorted halves into one sorted list

while l1 and l2:

compare nodes from both lists and attach smaller to merged list

tail.next = l1 if l1 else l2

attach remaining nodes after one list is exhausted

Output

1 -> 2 -> 3 -> 4 -> null

Complexity Analysis

Time: O(n log n) because the list is repeatedly split in half (log n splits) and merged (n operations per merge)

Space: O(log n) due to recursion stack depth from splitting the list

vs Alternative: Compared to bubble or insertion sort O(n²), merge sort is much faster for large lists

Edge Cases

empty list

returns None immediately without error

DSA Python

if not head or not head.next:

single element list

returns the single node as sorted

DSA Python

if not head or not head.next:

list with duplicate values

duplicates are kept and sorted correctly

DSA Python

while l1 and l2:

When to Use This Pattern

When you need to sort a linked list efficiently without converting it to an array, use merge sort because it works well with linked lists and avoids random access.

Common Mistakes

Mistake: Not splitting the list correctly by forgetting to set slow.next = None
Fix: Set slow.next = None to break the list into two separate halves

Mistake: Merging lists incorrectly by not updating tail pointer
Fix: Advance tail pointer after attaching a node to keep track of merged list end

Summary

Sorts a linked list by recursively splitting and merging sorted halves.

Use when you want an efficient O(n log n) sort for linked lists without extra array space.

The key is to split the list into halves, sort each half, then merge them back in order.