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.

Practice

1. What is the main advantage of using merge sort to sort a linked list compared to quicksort?

easy

A. Quicksort is unstable, but merge sort is always unstable.

B. Merge sort uses less memory than quicksort for linked lists.

C. Merge sort does not require random access, which suits linked lists well.

D. Merge sort sorts linked lists in-place without extra space.

Solution

1. Step 1: Understand linked list access

   Linked lists do not support fast random access, unlike arrays.

2. Step 2: Compare sorting algorithms

   Merge sort works by splitting and merging, which only needs sequential access, making it suitable for linked lists.

3. Final Answer:

   Merge sort does not require random access, which suits linked lists well. -> Option C

4. Quick Check:

   Linked list + merge sort = no random access needed [OK]

Hint: Merge sort fits linked lists because it uses sequential access [OK]

Common Mistakes:

• Thinking quicksort is better for linked lists
• Believing merge sort sorts in-place without extra space
• Confusing stability properties of sorting algorithms

2. Which of the following is the correct base case condition in a recursive merge sort function for a linked list?

easy

A. if head is None and head.next is None: return None

B. if head is None or head.next is None: return None

C. if head.next is None: return None

D. if head is None or head.next is None: return head

Solution

1. Step 1: Identify base case for recursion

   When the list is empty or has one node, it is already sorted.

2. Step 2: Correct base case condition

   Check if head is None (empty list) or head.next is None (single node), then return head.

3. Final Answer:

   if head is None or head.next is None: return head -> Option D

4. Quick Check:

   Base case returns head when list size ≤ 1 [OK]

Hint: Base case returns head if list empty or single node [OK]

Common Mistakes:

• Returning None instead of head for single node
• Using 'and' instead of 'or' in condition
• Missing base case leading to infinite recursion

3. What will be the output linked list after applying merge sort on the following linked list?

4 -> 2 -> 1 -> 3 -> None

medium

A. 1 -> 2 -> 3 -> 4 -> None

B. 4 -> 3 -> 2 -> 1 -> None

C. 2 -> 1 -> 3 -> 4 -> None

D. 1 -> 3 -> 2 -> 4 -> None

Solution

1. Step 1: Split the list into halves

   Split into (4 -> 2) and (1 -> 3).

2. Step 2: Recursively sort and merge

   Sort (4 -> 2) to (2 -> 4), sort (1 -> 3) to (1 -> 3), then merge to (1 -> 2 -> 3 -> 4).

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> None -> Option A

4. Quick Check:

   Sorted ascending order = 1 -> 2 -> 3 -> 4 [OK]

Hint: Merge sort outputs sorted list in ascending order [OK]

Common Mistakes:

• Confusing merge order and producing unsorted output
• Not splitting list correctly
• Merging without sorting halves first

4. Given this merge function snippet for linked lists, what is the bug?

def merge(left, right):
    if not left:
        return right
    if not right:
        return left
    if left.val < right.val:
        result = left
        result.next = merge(left.next, right)
    else:
        result = right
        result.next = merge(left, right.next)
    return result

medium

A. The comparison should be <= instead of < to maintain stability.

B. No bug; function correctly merges two sorted lists.

C. The function does not handle empty lists properly.

D. The function should return None at the end instead of result.

Solution

1. Step 1: Analyze base cases

   Returns right if left is None, and left if right is None, correctly handling empty lists.

2. Step 2: Check recursive merge logic

   Compares values, assigns result, and recursively merges remaining nodes correctly.

3. Final Answer:

   No bug; function correctly merges two sorted lists. -> Option B

4. Quick Check:

   Merge function logic is correct and complete [OK]

Hint: Check base cases and recursion carefully for merge correctness [OK]

Common Mistakes:

• Thinking <= is required for stability (not always needed)
• Missing base case returns
• Returning None instead of merged list

5. You have a linked list with nodes:

5 -> 3 -> 8 -> 2 -> 7 -> None

After applying merge sort, what will be the final linked list? Also, what is the time complexity of merge sort on this linked list?

hard

A. 2 -> 3 -> 5 -> 7 -> 8 -> None; Time complexity: O(n log n)

B. 2 -> 3 -> 5 -> 7 -> 8 -> None; Time complexity: O(n^2)

C. 5 -> 3 -> 8 -> 2 -> 7 -> None; Time complexity: O(n log n)

D. 3 -> 2 -> 5 -> 7 -> 8 -> None; Time complexity: O(n)

Solution

1. Step 1: Sort the linked list nodes

   Sorted order is 2 -> 3 -> 5 -> 7 -> 8.

2. Step 2: Understand merge sort time complexity

   Merge sort divides list and merges in O(n log n) time for n nodes.

3. Final Answer:

   2 -> 3 -> 5 -> 7 -> 8 -> None; Time complexity: O(n log n) -> Option A

4. Quick Check:

   Sorted list + merge sort time = O(n log n) [OK]

Hint: Merge sort always sorts in O(n log n) time [OK]

Common Mistakes:

• Confusing time complexity with O(n^2)
• Not sorting nodes correctly
• Assuming merge sort is O(n)