Sort a Linked List Using Merge Sort in DSA Rust - Deep Dive

Overview - Sort a Linked List Using Merge Sort

What is it?

Merge sort is the standard algorithm for sorting a linked list because it achieves O(n log n) time with O(log n) stack space (for recursion) and O(1) extra data space — unlike array merge sort which needs O(n) auxiliary space. The algorithm splits the list at the middle, recursively sorts both halves, then merges the sorted halves in O(n) time.

Why it matters

Sorting a linked list demonstrates mastery of both pointer manipulation and divide-and-conquer strategy. In Rust, this problem is particularly instructive because Rust's ownership system makes in-place linked list manipulation explicit — you must consciously manage ownership when splitting and merging nodes.

Where it fits

You need comfort with Rust's Box, Option>, and recursive ownership patterns before tackling this. After mastering it, merge K sorted lists and inplace reversal follow naturally.

Mental Model

Core Idea

Split the list in half repeatedly until each piece has one node, then merge pieces back together in sorted order — like sorting a deck of cards by splitting it into pairs, sorting each pair, then merging pairs into fours, and so on.

Think of it like...

Sorting a deck of cards by repeatedly splitting into two piles and merging them back in order. Each merge step is simple — just compare the top card of each pile and take the smaller one.

Original:  4 → 2 → 1 → 3

Split:     4 → 2  |  1 → 3
Split:     4 | 2  |  1 | 3

Merge:    [2→4]  |  [1→3]
Merge:     1→2→3→4  ✓

Build-Up - 5 Steps

1

Foundation

Why Merge Sort — Not Quick Sort — for Linked Lists

Concept: Merge sort is preferred for linked lists because split is O(n) via slow/fast pointer, while quick sort's random access pivot selection is O(n) per level.

Quick sort on arrays works because we can access any element in O(1) to choose a pivot. Linked lists have no random access — finding the kth element takes O(k). Merge sort's split operation uses the slow/fast pointer technique to find the midpoint in O(n), and the merge step is O(n) with only pointer reassignment — no extra array needed. This makes merge sort O(n log n) time and O(1) data space for linked lists.

Result

Merge sort is the canonical O(n log n) algorithm for linked lists.

The choice of sorting algorithm should match the data structure's access pattern. Linked lists favor merge sort; arrays favor quick sort or heap sort.

2

Foundation

Finding the Middle — Slow/Fast Pointer in Rust

Concept: Use two pointers: slow advances one step, fast advances two steps — when fast reaches the end, slow is at the middle.

In Rust with Box: traverse with immutable references to find mid. Since Box gives unique ownership, splitting requires taking ownership at the midpoint. The split function returns (first_half, second_half) as two Option> values. Specifically: advance to the node BEFORE the midpoint, then take its next pointer to get the second half, leaving first half intact.

Result

List split into two independent halves with correct ownership.

Rust's ownership model makes the split explicit — you must 'take' the second half's Box, which automatically severs the connection. No pointer nulling needed.

3

Intermediate

Merge Two Sorted Lists — Rust Ownership Pattern

🤔Before reading on: when merging two sorted lists in Rust, how do you decide which node goes first without violating ownership? Commit to your approach.

Concept: Compare head values, take the smaller head, recursively merge the rest.

Merge takes ownership of both lists. Compare l1.val and l2.val. Take the node with smaller value by unwrapping the Box. Set that node's next to the result of recursively merging the remaining lists. Return the taken node wrapped in Some(Box::new(...)). Rust's move semantics ensure no node is ever owned by two places simultaneously.

Result

Merged sorted list with correct ownership — no raw pointer manipulation needed.

Rust's recursive merge is clean: take the minimum head, recursively merge, chain. The ownership model prevents double-free and use-after-free automatically.

4

Intermediate

Full Merge Sort — Recursive Structure

🤔Before reading on: what is the base case for merge sort on a linked list? Commit to your answer.

Concept: Base case: list with 0 or 1 nodes is already sorted. Recursive case: split, sort each half, merge.

fn merge_sort(head: Option>) -> Option> { 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) }. The recursion depth is O(log n) — each level halves the list.

Result

Complete O(n log n) merge sort consuming the original list and returning a sorted one.

The base case (0 or 1 nodes) terminates recursion. Rust's move semantics ensure the original list is consumed — no dangling references.

5

Advanced

Iterative Bottom-Up Merge Sort for O(1) Stack Space

🤔Before reading on: does recursive merge sort on a linked list use O(log n) or O(1) stack space? Can we do better? Commit to your answer.

Concept: Bottom-up merge sort merges sublists of size 1, then 2, then 4, avoiding recursion.

Start with sublists of size 1 (each node). Merge adjacent pairs to get sorted sublists of size 2. Repeat with size 4, 8, ... until the whole list is sorted. This avoids the O(log n) recursive call stack, achieving true O(1) extra space. Implementation requires careful pointer management to link merged sublists and track the remaining unprocessed list.

Result

O(n log n) time, O(1) space — optimal for linked list sorting.

The iterative version is harder to implement but demonstrates the same algorithm without recursion overhead — important for embedded or stack-constrained environments.

Under the Hood

Merge sort works by the divide-and-conquer principle: splitting is O(n) using slow/fast pointer, each of the log n levels processes all n nodes for O(n) work per level, totaling O(n log n). The merge step only reassigns next pointers — no new nodes are created. Total extra space: O(log n) for the recursion stack (O(1) for iterative version).

Why designed this way?

Merge sort is stable (preserves relative order of equal elements) and makes exactly O(n log n) comparisons in all cases — no worst-case O(n²) like quick sort. For linked lists where random access is O(n), the sequential nature of merge sort's data access pattern perfectly matches the sequential traversal capability of linked lists.

4 → 2 → 1 → 3

Level 0 (split):
  Left:  4 → 2
  Right: 1 → 3

Level 1 (split again):
  4 | 2 | 1 | 3  (single nodes)

Level 1 (merge pairs):
  2→4  and  1→3

Level 0 (merge halves):
  Compare: 2→4 with 1→3
  1 < 2 → take 1, merge 2→4 with 3
  2 < 3 → take 2, merge 4 with 3
  3 < 4 → take 3, merge 4 with None
  take 4
  Result: 1→2→3→4

Myth Busters - 2 Common Misconceptions

Quick: does merge sort on a linked list need O(n) extra space like on arrays? Commit yes or no.

Common Belief: Merge sort always needs O(n) extra space for the auxiliary array.

Reality: Linked list merge sort needs only O(log n) stack space (recursive) or O(1) (iterative). No auxiliary array is needed — nodes are relinked in place.

Why it matters: This is the key advantage over array merge sort — linked list merge sort is space-efficient because merging reuses existing nodes.

Quick: is quick sort faster than merge sort for linked lists? Commit yes or no.

Common Belief: Quick sort is always O(n log n) average and faster in practice than merge sort.

Reality: For linked lists, quick sort's O(1) random access pivot advantage disappears. Pivot selection takes O(n) via traversal, and partition is harder to implement correctly. Merge sort is preferred for linked lists.

Why it matters: Algorithm choice depends on data structure access patterns. Quick sort = random access advantage. Merge sort = sequential access strength.

Expert Zone

1

Rust's Box makes split explicit — you take the Box at the midpoint, which transfers ownership and severs the link without any pointer nulling.

2

The slow/fast pointer for finding mid should stop when fast.next is None (not fast.next.next is None) to ensure the left half is shorter or equal for odd-length lists — preventing infinite recursion.

3

In competitive Rust, linked lists are often represented as Vec to avoid Box overhead. For interview problems, Box is standard.

When NOT to use

If you need in-place sorting without recursion and the list fits in memory, converting to Vec, sorting with .sort(), and rebuilding the list avoids pointer complexity. For production Rust code, std::collections::LinkedList is rarely used — BTreeMap or Vec<> are preferred.

Production Patterns

Merge sort on linked lists appears in external sorting (sorting data too large for memory by merging sorted chunks), database merge joins (merging sorted result sets), and distributed systems merge operations.

Connections

Merge K Sorted Lists

Merge sort's merge step is exactly the two-list merge used in Merge K Sorted Lists — mastering one directly enables the other.

Merge K sorted lists extends the binary merge to k-way merge using a min-heap — the same merge logic, applied at scale.

Slow/Fast Pointer (Tortoise and Hare)

Finding the middle of a linked list uses the same slow/fast pointer technique as cycle detection — both advance at different speeds.

The slow/fast pointer is a universal linked list tool: middle-finding (for merge sort), cycle detection (Floyd's), and kth-from-end all use the same pattern.

Common Pitfalls

#1 Stopping fast pointer at wrong position, creating unequal splits.

Wrong approach:

// Fast stops when fast is None — slow ends up too far right
while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
slow = slow.next;
fast = fast.next.next; // Goes one step too far
}

Correct approach:

// Fast stops when fast.next.next is None — slow points to node BEFORE mid
while fast.as_ref().unwrap().next.is_some()
&& fast.as_ref().unwrap().next.as_ref().unwrap().next.is_some() {
slow = slow.next.as_mut().unwrap();
fast = fast.next.next.next; // Correct stopping
}

Root cause:

The stopping condition determines where slow ends up. To split properly, slow should point to the last node of the first half — its next pointer gives the second half.

#2 Not handling single-node and empty list base cases.

Wrong approach:

fn merge_sort(head: Option>) -> Option> {
// Missing base case — infinite recursion on single node
let (left, right) = split(head);
...
}

Correct approach:

fn merge_sort(head: Option>) -> Option> {
if head.is_none() || head.as_ref().unwrap().next.is_none() {
return head; // Already sorted
}
let (left, right) = split(head);
...
}

Root cause:

Without base case checking, split() on a single-node list returns (Some(node), None) — the recursive call on Some(node) never terminates.

Key Takeaways

Merge sort is the standard O(n log n) algorithm for linked lists — quick sort's random access advantage disappears with sequential-access nodes.

No auxiliary array needed — linked list merge sort relinks existing nodes in O(n) per level, using only O(log n) stack space.

Rust's Box makes split explicit: taking the Box at the midpoint transfers ownership and severs the link atomically.

Slow/fast pointer finds the midpoint in O(n) — slow advances one step per iteration, fast advances two.

Bottom-up iterative merge sort achieves O(1) space by merging sublists of size 1, 2, 4, ... without recursion.

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