Sort a Linked List Using Merge Sort in DSA Rust

Mental Model

Split the list into halves, sort each half, then merge them back in order. Repeat until the whole list is sorted.

Analogy: Like sorting a deck of cards by splitting it into smaller piles, sorting each pile, then carefully merging them back 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 the list helps to sort smaller parts recursively

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

2 -> 4 -> null

Why: Sorting smaller halves makes merging easier

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

1 -> 3 -> null

Why: Right half is already sorted or smaller

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

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

Why: Merging combines sorted halves into a fully sorted list

Result:

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

Annotated Code

DSA Rust

use std::fmt::{self, Display};

#[derive(Debug)]
struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

impl ListNode {
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

struct LinkedList {
    head: Option<Box<ListNode>>,
}

impl LinkedList {
    fn new() -> Self {
        LinkedList { head: None }
    }

    fn push(&mut self, val: i32) {
        let new_node = Box::new(ListNode { val, next: self.head.take() });
        self.head = Some(new_node);
    }

    fn merge_sort(&mut self) {
        self.head = Self::merge_sort_list(self.head.take());
    }

    fn merge_sort_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        // Base case: empty or single node
        if head.is_none() || head.as_ref().unwrap().next.is_none() {
            return head;
        }

        // Split list into two halves
        let (left, right) = Self::split(head);

        // Recursively sort each half
        let sorted_left = Self::merge_sort_list(left);
        let sorted_right = Self::merge_sort_list(right);

        // Merge sorted halves
        Self::merge(sorted_left, sorted_right)
    }

    fn split(mut head: Option<Box<ListNode>>) -> (Option<Box<ListNode>>, Option<Box<ListNode>>) {
        if head.is_none() || head.as_ref().unwrap().next.is_none() {
            return (head, None);
        }

        let mut slow = head.as_mut();
        let mut fast = head.as_ref().unwrap().next.as_ref();

        while fast.is_some() && fast.unwrap().next.is_some() {
            fast = fast.unwrap().next.as_ref().unwrap().next.as_ref();
            slow = slow.unwrap().next.as_mut();
        }

        let mid = slow.unwrap().next.take();
        (head, mid)
    }

    fn merge(
        list1: Option<Box<ListNode>>,
        list2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        match (list1, list2) {
            (None, None) => None,
            (Some(node), None) | (None, Some(node)) => Some(node),
            (Some(mut node1), Some(mut node2)) => {
                if node1.val < node2.val {
                    let next = node1.next.take();
                    node1.next = Self::merge(next, Some(node2));
                    Some(node1)
                } else {
                    let next = node2.next.take();
                    node2.next = Self::merge(Some(node1), next);
                    Some(node2)
                }
            }
        }
    }

    fn print(&self) {
        let mut curr = self.head.as_ref();
        while let Some(node) = curr {
            print!("{} -> ", node.val);
            curr = node.next.as_ref();
        }
        println!("null");
    }
}

fn main() {
    let mut list = LinkedList::new();
    // Push elements in reverse order to create 4 -> 2 -> 1 -> 3
    list.push(3);
    list.push(1);
    list.push(2);
    list.push(4);

    println!("Original list:");
    list.print();

    list.merge_sort();

    println!("Sorted list:");
    list.print();
}

if head.is_none() || head.as_ref().unwrap().next.is_none() { return head; }

Base case: stop recursion when list is empty or has one node

let (left, right) = Self::split(head);

Split list into two halves using slow and fast pointers

let sorted_left = Self::merge_sort_list(left);

Recursively sort left half

let sorted_right = Self::merge_sort_list(right);

Recursively sort right half

Self::merge(sorted_left, sorted_right)

Merge two sorted halves into one sorted list

if node1.val < node2.val { ... } else { ... }

Compare nodes to merge in sorted order

Output

Original list:

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

Sorted list:

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

Complexity Analysis

Time: O(n log n) because the list is split in half log n times and merging takes O(n) each time

Space: O(log n) due to recursion stack depth for splitting

vs Alternative: Better than bubble or insertion sort on linked list which are O(n^2), merge sort is efficient for linked lists

Edge Cases

empty list

returns immediately without error

DSA Rust

if head.is_none() || head.as_ref().unwrap().next.is_none() { return head; }

single element list

returns the single node as sorted

DSA Rust

if head.is_none() || head.as_ref().unwrap().next.is_none() { return head; }

list with duplicate values

duplicates are kept and sorted correctly

DSA Rust

if node1.val < node2.val { ... } else { ... }

When to Use This Pattern

When you need to sort a linked list efficiently, use merge sort because it splits and merges without random access.

Common Mistakes

Mistake: Not breaking the list properly during split causing infinite recursion
Fix: Ensure to cut the list by setting the middle node's next to None

Mistake: Merging nodes incorrectly by not updating next pointers properly
Fix: Always take ownership of next pointers and assign merged results carefully

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.

The key is to split the list into halves and merge sorted parts back together.

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