Sort a Linked List Using Merge Sort in DSA Rust - 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 list

No↓

Split list into two halves

↓

Recursively sort left half

↓

Merge two sorted halves

↓

Return merged sorted list

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

Execution Sample

DSA Rust

fn merge_sort(head: Option<Box<Node>>) -> Option<Box<Node>> {
    if head.is_none() || head.as_ref().unwrap().next.is_none() {
        return head;
    }
    let (left, right) = split(head);
    let sorted_left = merge_sort(left);
    let sorted_right = merge_sort(right);
    merge(sorted_left, sorted_right)
}

This function sorts a linked list by splitting it recursively and merging sorted halves.

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 node 4	4 -> 2 -> 1 -> 3 -> null
2	Check base case	4 nodes	No change	4 -> 2 -> 1 -> 3 -> null
3	Split list into halves	Left half: 4 -> 2 -> null, Right half: 1 -> 3 -> null	Left head points to 4, Right head points to 1	Left: 4 -> 2 -> null | Right: 1 -> 3 -> null
4	Recursively sort left half	2 nodes: 4 -> 2 -> null	head points to 4	4 -> 2 -> null
5	Split left half	Left: 4 -> null, Right: 2 -> null	Left head points to 4, Right head points to 2	Left: 4 -> null | Right: 2 -> null
6	Sort left-left half (single node)	1 node: 4 -> null	No change	4 -> null
7	Sort left-right half (single node)	1 node: 2 -> null	No change	2 -> null
8	Merge left halves	2 nodes sorted: 2 -> 4 -> null	Pointers rearranged to merge	2 -> 4 -> null
9	Recursively sort right half	2 nodes: 1 -> 3 -> null	head points to 1	1 -> 3 -> null
10	Split right half	Left: 1 -> null, Right: 3 -> null	Left head points to 1, Right head points to 3	Left: 1 -> null | Right: 3 -> null
11	Sort right-left half (single node)	1 node: 1 -> null	No change	1 -> null
12	Sort right-right half (single node)	1 node: 3 -> null	No change	3 -> null
13	Merge right halves	2 nodes sorted: 1 -> 3 -> null	Pointers rearranged to merge	1 -> 3 -> null
14	Merge two sorted halves	4 nodes sorted: 1 -> 2 -> 3 -> 4 -> null	Pointers rearranged to merge	1 -> 2 -> 3 -> 4 -> null
15	Return sorted list	4 nodes sorted	head points to 1	1 -> 2 -> 3 -> 4 -> null
16	Exit	Sorting complete	No change	1 -> 2 -> 3 -> 4 -> null

💡 All nodes merged and sorted, recursion ends

Variable Tracker

Variable	Start	After Step 3	After Step 8	After Step 13	After Step 14	Final
head	4 -> 2 -> 1 -> 3 -> null	Left: 4 -> 2 -> null, Right: 1 -> 3 -> null	2 -> 4 -> null	1 -> 3 -> null	1 -> 2 -> 3 -> 4 -> null	1 -> 2 -> 3 -> 4 -> null
left	None	4 -> 2 -> null	4 -> null	None	None	None
right	None	1 -> 3 -> null	None	1 -> null	3 -> null	None

Key Moments - 3 Insights

Why do we split the list into two halves instead of sorting directly?

Splitting breaks the problem into smaller parts that are easier to sort. The execution_table rows 3 and 5 show how the list is divided to apply merge sort recursively.

How do we know when to stop splitting the list?

When the list has zero or one node, it is already sorted. This is checked in step 2 and seen in steps 6, 7, 11, and 12 where single nodes are returned without further splitting.

How does merging keep the list sorted?

Merging compares nodes from two sorted halves and links them in order. Steps 8, 13, and 14 show pointers rearranged to merge sorted halves into a sorted list.

Visual Quiz - 3 Questions

Look at the execution_table, what is the visual state after step 8?

A 1 -> 3 -> null

B 2 -> 4 -> null

C 4 -> 2 -> null

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

💡 Hint

Check the Visual State column at step 8 in the execution_table

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

A Step 2

B Step 5

C Step 3

D Step 9

💡 Hint

Look at the Operation column for the first 'Split list into halves' in the execution_table

If the original list had only one node, what would happen at step 2?

A The function would return the list immediately

B The list would be split into halves

C The list would be merged

D The function would crash

💡 Hint

Step 2 checks the base case for list length in the execution_table

Concept Snapshot

Sort a linked list using merge sort:
- Base case: empty or single node list is sorted
- Split list into two halves using slow/fast pointers
- Recursively sort each half
- Merge two sorted halves by comparing nodes
- Result is a 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. These small lists are already sorted. Then, the merge step combines two sorted lists into one sorted list by comparing node values and linking them in order. This process repeats until the entire list is sorted. The execution trace shows starting with a list of four nodes, splitting it into halves, sorting each half recursively, and merging them back to get a sorted list. Key points include stopping recursion at single nodes and merging sorted halves carefully to maintain order.

Practice

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

easy

A. Merge sort is faster than quicksort in all cases.

B. Merge sort uses less memory than quicksort.

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

D. Merge sort sorts the list 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 well with sequential access by splitting and merging, while quicksort relies on random access for partitioning.

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 avoids random access [OK]

Common Mistakes:

• Thinking quicksort is always faster
• Assuming merge sort sorts in place without extra space
• Confusing memory usage between merge sort and quicksort

2. Which Rust code snippet correctly defines a singly linked list node struct for merge sort?

easy

A. struct ListNode { val: i32, next: Box<ListNode> }

B. struct ListNode { val: i32, next: Option }

C. struct ListNode { val: i32, next: &ListNode }

D. struct ListNode { val: i32, next: Option<&ListNode> }

Solution

1. Step 1: Understand ownership in Rust linked lists

   Rust requires ownership for heap data; Box<T> owns heap data, Option allows None or a node.

2. Step 2: Analyze options

   struct ListNode { val: i32, next: Option } uses Option which is correct for nullable next pointer. Others use references without ownership or missing Option.

3. Final Answer:

   struct ListNode { val: i32, next: Option } -> Option B

4. Quick Check:

   Rust linked list node uses Option [OK]

Hint: Use Option for nullable next in Rust linked lists [OK]

Common Mistakes:

• Using references (&) without lifetime management
• Omitting Option for nullable next pointer
• Using Box<T> without Option causing no null

3. Given the following linked list: 4 -> 2 -> 1 -> 3 -> null, what is the sorted list after applying merge sort?

medium

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

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

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

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

Solution

1. Step 1: Split the list into halves

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

2. Step 2: Recursively sort and merge

   Sort halves: 4->2 becomes 2->4, 1->3 becomes 1->3. Merge sorted halves: 1->2->3->4.

3. Final Answer:

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

4. Quick Check:

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

Hint: Merge sort splits and merges sorted halves for linked lists [OK]

Common Mistakes:

• Not splitting list correctly
• Merging without sorting halves
• Confusing order of merged nodes

4. In the Rust merge sort implementation for linked lists, which mistake causes infinite recursion?

medium

A. Using Box instead of Rc for next pointers

B. Using a mutable reference instead of ownership for nodes

C. Sorting the list without splitting it

D. Not updating the next pointer to None when splitting the list

Solution

1. Step 1: Understand splitting in merge sort

   Splitting requires breaking the list into two halves by setting the middle node's next pointer to None.

2. Step 2: Identify infinite recursion cause

   If next pointer is not set to None, recursive calls never reach base case, causing infinite recursion.

3. Final Answer:

   Not updating the next pointer to None when splitting the list -> Option D

4. Quick Check:

   Broken split causes infinite recursion [OK]

Hint: Set middle.next = None to stop recursion [OK]

Common Mistakes:

• Forgetting to break the list at midpoint
• Confusing Box and Rc usage
• Misusing references causing borrow errors

5. You have a linked list with duplicate values: 5 -> 3 -> 5 -> 2 -> 3 -> null. After applying merge sort, what is the correct sorted list?

hard

A. 2 -> 3 -> 3 -> 5 -> 5 -> null

B. 5 -> 5 -> 3 -> 3 -> 2 -> null

C. 2 -> 3 -> 5 -> null

D. 3 -> 2 -> 5 -> 3 -> 5 -> null

Solution

1. Step 1: Recognize duplicates in the list

   The list contains duplicates: two 5s and two 3s.

2. Step 2: Apply merge sort preserving duplicates

   Merge sort sorts all nodes including duplicates, resulting in ascending order with duplicates preserved: 2->3->3->5->5.

3. Final Answer:

   2 -> 3 -> 3 -> 5 -> 5 -> null -> Option A

4. Quick Check:

   Sorted list keeps duplicates in order [OK]

Hint: Merge sort keeps duplicates sorted in order [OK]

Common Mistakes:

• Removing duplicates by mistake
• Sorting incorrectly ignoring duplicates
• Confusing output order with duplicates