Sort a Linked List Using Merge Sort in DSA Python - Execution Trace

Concept Flow - Sort a Linked List Using Merge Sort

Start with head of list

↓

Base case: list empty or one node?

Yes→Return head

No↓

Split list into two halves

↓

Recursively sort left half

↓

Merge two sorted halves

↓

Return merged list

The list is split into halves recursively until single nodes remain, then merged back in sorted order.

Execution Sample

DSA Python

def merge_sort(head):
    if not head or not head.next:
        return head
    mid = get_middle(head)
    right = mid.next
    mid.next = None
    left_sorted = merge_sort(head)
    right_sorted = merge_sort(right)
    return merge(left_sorted, right_sorted)

This code splits the linked list, sorts each half recursively, and merges them.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with full list	4 nodes: 4 -> 2 -> 1 -> 3 -> null	head points to 4	4 -> 2 -> 1 -> 3 -> null
2	Find middle node	4 nodes: 4 -> 2 -> 1 -> 3 -> null	mid points to 2	4 -> 2 -> 1 -> 3 -> null
3	Split list at mid	Left: 4 -> 2 -> null, Right: 1 -> 3 -> null	mid.next = None	4 -> 2 -> null and 1 -> 3 -> null
4	Recursively sort left half	2 nodes: 4 -> 2 -> null	head points to 4	4 -> 2 -> null
5	Find middle of left half	2 nodes: 4 -> 2 -> null	mid points to 4	4 -> 2 -> null
6	Split left half	Left: 4 -> null, Right: 2 -> null	mid.next = None	4 -> null and 2 -> null
7	Sort left part of left half (single node)	1 node: 4 -> null	Return head	4 -> null
8	Sort right part of left half (single node)	1 node: 2 -> null	Return head	2 -> null
9	Merge sorted left parts	Left: 4 -> null, Right: 2 -> null	Merge 4 and 2	2 -> 4 -> null
10	Recursively sort right half	2 nodes: 1 -> 3 -> null	head points to 1	1 -> 3 -> null
11	Find middle of right half	2 nodes: 1 -> 3 -> null	mid points to 1	1 -> 3 -> null
12	Split right half	Left: 1 -> null, Right: 3 -> null	mid.next = None	1 -> null and 3 -> null
13	Sort left part of right half (single node)	1 node: 1 -> null	Return head	1 -> null
14	Sort right part of right half (single node)	1 node: 3 -> null	Return head	3 -> null
15	Merge sorted right parts	Left: 1 -> null, Right: 3 -> null	Merge 1 and 3	1 -> 3 -> null
16	Merge two sorted halves	Left: 2 -> 4 -> null, Right: 1 -> 3 -> null	Merge 2->4 and 1->3	1 -> 2 -> 3 -> 4 -> null
17	Return fully sorted list	4 nodes: 1 -> 2 -> 3 -> 4 -> null	head points to 1	1 -> 2 -> 3 -> 4 -> null
18	End	Sorted list returned	No pointer changes	1 -> 2 -> 3 -> 4 -> null

💡 Recursion ends when sublist has 0 or 1 node, then merges build sorted list back up.

Variable Tracker

Variable	Start	After Step 3	After Step 9	After Step 15	Final
head	4 -> 2 -> 1 -> 3 -> null	4 -> 2 -> null	2 -> 4 -> null	1 -> 3 -> null	1 -> 2 -> 3 -> 4 -> null
mid	None	2 -> null	4 -> null	1 -> null	null
left_sorted	None	None	2 -> 4 -> null	2 -> 4 -> null	2 -> 4 -> null
right_sorted	None	None	None	1 -> 3 -> null	1 -> 3 -> null

Key Moments - 3 Insights

Why do we split the list at mid.next and set mid.next = None?

Splitting at mid.next breaks the list into two separate halves so recursion can sort each half independently. See Step 3 where mid.next is set to None to separate left and right halves.

Why does recursion stop when the list has one or zero nodes?

A list with zero or one node is already sorted, so recursion returns immediately. This is shown in Steps 7, 8, 13, and 14 where single-node lists return head.

How does merging two sorted lists maintain order?

Merge compares nodes from each half and links the smaller node first, building a sorted list. Step 9 and Step 15 show merging two single-node lists into sorted two-node lists.

Visual Quiz - 3 Questions

Look at the execution table, what is the visual state after Step 9?

A 4 -> 2 -> null

B 1 -> 3 -> null

C 2 -> 4 -> null

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

💡 Hint

Check the 'Visual State' column for Step 9 in the execution_table.

At which step does the recursion first split the list into two halves?

A Step 3

B Step 6

C Step 2

D Step 11

💡 Hint

Look for the step where 'Split list at mid' happens in the execution_table.

If the original list had only one node, what would happen in the execution?

A Merge would be called immediately

B Function would return head immediately

C Recursion would continue splitting

D List would be split into two empty lists

💡 Hint

Refer to the base case condition in the code and Steps 7, 8, 13, 14 in execution_table.

Concept Snapshot

Merge Sort on Linked List:
- Base case: empty or single node list returns as is
- Find middle node using slow/fast pointers
- Split list into two halves at middle
- Recursively sort each half
- Merge two sorted halves into one sorted list
- Returns fully sorted linked list

Full Transcript

Merge sort on a linked list works by splitting the list into two halves recursively until each sublist has one or zero nodes, which are inherently sorted. Then, it merges these sorted sublists back together in order. The process starts by finding the middle node to split the list. The split is done by setting the middle node's next pointer to None, separating the list into two halves. Each half is sorted recursively by the same method. Finally, the two sorted halves are merged by comparing nodes one by one and linking the smaller node first. This continues until the entire list is sorted. The recursion stops when the sublist has one or zero nodes. The final result is a fully sorted linked list.