Why Sort a Linked List Using Merge Sort in DSA Rust?

The Big Idea

What if you could sort a messy list quickly without losing track or making mistakes?

The Scenario

Imagine you have a messy stack of papers with numbers written on them. You want to arrange them from smallest to largest. If you try to do this by picking random papers and comparing them one by one, it will take a long time and you might make mistakes.

The Problem

Trying to sort a linked list by checking every pair manually is slow and confusing. You have to jump from one paper to another without a clear order, which can cause you to lose track or repeat steps. This makes the process very tiring and error-prone.

The Solution

Merge sort breaks the messy stack into smaller piles, sorts each pile easily, and then carefully combines them back in order. This way, you never get lost, and sorting becomes faster and more reliable, even for long lists.

Before vs After

✗ Before

fn sort_linked_list(head: Option<Box<Node>>) -> Option<Box<Node>> {
    // manually compare and swap nodes repeatedly
    // very complex and slow
    head
}

✓ After

fn merge_sort(head: Option<Box<Node>>) -> Option<Box<Node>> {
    // split list, sort halves, merge sorted halves
    // efficient and clean
    head
}

What It Enables

It lets you quickly and safely organize linked lists of any size, making your programs faster and easier to understand.

Real Life Example

Sorting a playlist of songs stored as a linked list by their play counts, so your favorite songs come first without losing any track.

Key Takeaways

Manual sorting of linked lists is slow and error-prone.

Merge sort breaks the list into smaller parts, sorts, and merges them efficiently.

This method works well even for very long linked lists.

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