Sort a Linked List Using Merge Sort in DSA Rust - Build from Scratch

Sort a Linked List Using Merge Sort

📖 Scenario: You work at a company that manages a list of tasks. Each task is stored as a node in a linked list. The tasks are currently unordered, and you need to sort them by their priority number to help the team work efficiently.

🎯 Goal: Build a Rust program that creates a linked list of tasks, then sorts the list using the merge sort algorithm. Finally, print the sorted list showing task priorities in order.

📋 What You'll Learn

Create a singly linked list with nodes containing integer priorities

Implement a function to split the linked list into halves

Implement the merge sort algorithm to sort the linked list by priority

Print the sorted linked list priorities in order

💡 Why This Matters

🌍 Real World

Sorting linked lists is useful in many applications like task scheduling, memory management, and real-time data processing where data is naturally linked.

💼 Career

Understanding linked list sorting and merge sort is important for software engineers working on system programming, embedded systems, and performance-critical applications.

1

Create the Linked List with Task Priorities

Create a singly linked list struct called ListNode with a field priority: i32 and a next pointer. Then create a linked list called head with these exact priorities in order: 4, 2, 5, 1, 3.

DSA Rust

// Define ListNode struct and create linked list head with priorities 4 -> 2 -> 5 -> 1 -> 3
// Your code here

Hint

Define a struct with priority and next. Use Box to create the linked list nodes. Link nodes by setting next fields.

2

Add a Helper Function to Print the Linked List

Add a function called print_list that takes a reference to Option<Box<ListNode>> and prints the priorities in order separated by -> and ending with null.

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
pub struct ListNode {
    pub priority: i32,
    pub next: Option>,
}

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

fn print_list(head: &Option>) {
    // Your code here
}

fn main() {
    let mut head = Box::new(ListNode::new(4));
    head.next = Some(Box::new(ListNode::new(2)));
    head.next.as_mut().unwrap().next = Some(Box::new(ListNode::new(5)));
    head.next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(ListNode::new(1)));
    head.next.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(ListNode::new(3)));
}

Hint

Use a while let loop to traverse the list. Print each priority followed by -> . End with null.

3

Implement Merge Sort for the Linked List

Implement a function called merge_sort that takes Option<Box<ListNode>> and returns a sorted Option<Box<ListNode>> by priority using merge sort. Also implement helper functions split_list to split the list into halves and merge to merge two sorted lists.

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
pub struct ListNode {
    pub priority: i32,
    pub next: Option>,
}

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

fn print_list(head: &Option>) {
    let mut current = head;
    while let Some(node) = current {
        print!("{} -> ", node.priority);
        current = &node.next;
    }
    println!("null");
}

fn split_list(head: Option>) -> (Option>, Option>) {
    // Your code here
}

fn merge(l1: Option>, l2: Option>) -> Option> {
    // Your code here
}

fn merge_sort(head: Option>) -> Option> {
    // Your code here
}

fn main() {
    let mut head = Box::new(ListNode::new(4));
    head.next = Some(Box::new(ListNode::new(2)));
    head.next.as_mut().unwrap().next = Some(Box::new(ListNode::new(5)));
    head.next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(ListNode::new(1)));
    head.next.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(ListNode::new(3)));

    print_list(&Some(head));
}

Hint

Use the fast and slow pointer technique in split_list to find the middle. Recursively sort left and right halves in merge_sort. Merge sorted halves in merge.

4

Sort the List and Print the Sorted Priorities

Call merge_sort on the linked list head and store the result in sorted_head. Then call print_list with &sorted_head to print the sorted priorities.

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
pub struct ListNode {
    pub priority: i32,
    pub next: Option>,
}

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

fn print_list(head: &Option>) {
    let mut current = head;
    while let Some(node) = current {
        print!("{} -> ", node.priority);
        current = &node.next;
    }
    println!("null");
}

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

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

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

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

fn merge(l1: Option>, l2: Option>) -> Option> {
    match (l1, l2) {
        (None, None) => None,
        (Some(list), None) => Some(list),
        (None, Some(list)) => Some(list),
        (Some(mut list1), Some(mut list2)) => {
            if list1.priority >) -> Option> {
    if head.is_none() || head.as_ref().unwrap().next.is_none() {
        return head;
    }

    let (left, right) = split_list(head);
    let sorted_left = merge_sort(left);
    let sorted_right = merge_sort(right);

    merge(sorted_left, sorted_right)
}

fn main() {
    let mut head = Box::new(ListNode::new(4));
    head.next = Some(Box::new(ListNode::new(2)));
    head.next.as_mut().unwrap().next = Some(Box::new(ListNode::new(5)));
    head.next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(ListNode::new(1)));
    head.next.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(ListNode::new(3)));

    // Your code here
}

Hint

Call merge_sort on Some(head) and save to sorted_head. Then call print_list(&sorted_head) to print the sorted list.

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