Merge Sort as Divide and Conquer in DSA Rust

Mental Model

Split the list into smaller parts, sort each part, then join them back in order.

Analogy: Imagine sorting a big pile of cards by splitting it into smaller piles, sorting each pile, then carefully combining them back into one sorted pile.

Unsorted list:
[38, 27, 43, 3, 9, 82, 10]

Split into halves:
[38, 27, 43]   [3, 9, 82, 10]

Split further:
[38] [27, 43]   [3, 9] [82, 10]

Sorted small parts:
[27, 38, 43]   [3, 9, 10, 82]

Merged sorted list:
[3, 9, 10, 27, 38, 43, 82]

Dry Run Walkthrough

Input: list: [38, 27, 43, 3, 9, 82, 10]

Goal: Sort the list in ascending order using merge sort

Step 1: Split list into two halves

[38, 27, 43]   [3, 9, 82, 10]

Why: Divide the problem into smaller parts to handle sorting easier

Step 2: Split left half into smaller parts

[38]   [27, 43]   [3, 9, 82, 10]

Why: Keep dividing until parts have one element

Step 3: Split right half into smaller parts

[38]   [27, 43]   [3, 9]   [82, 10]

Why: Divide right half similarly to left half

Step 4: Split [27, 43] into [27] and [43]

[38]   [27]   [43]   [3, 9]   [82, 10]

Why: Continue splitting until single elements

Step 5: Split [3, 9] into [3] and [9]

[38]   [27]   [43]   [3]   [9]   [82, 10]

Why: Split right side further

Step 6: Split [82, 10] into [82] and [10]

[38]   [27]   [43]   [3]   [9]   [82]   [10]

Why: Split last pair into single elements

Step 7: Merge [27] and [43] into sorted [27, 43]

[38]   [27, 43]   [3]   [9]   [82]   [10]

Why: Start merging sorted parts

Step 8: Merge [3] and [9] into sorted [3, 9]

[38]   [27, 43]   [3, 9]   [82]   [10]

Why: Merge right side small parts

Step 9: Merge [82] and [10] into sorted [10, 82]

[38]   [27, 43]   [3, 9]   [10, 82]

Why: Merge last pair sorted

Step 10: Merge [38] and [27, 43] into sorted [27, 38, 43]

[27, 38, 43]   [3, 9]   [10, 82]

Why: Merge left side parts

Step 11: Merge [3, 9] and [10, 82] into sorted [3, 9, 10, 82]

[27, 38, 43]   [3, 9, 10, 82]

Why: Merge right side parts

Step 12: Merge [27, 38, 43] and [3, 9, 10, 82] into final sorted list

[3, 9, 10, 27, 38, 43, 82]

Why: Combine all sorted parts into one sorted list

Result:

[3, 9, 10, 27, 38, 43, 82]

Annotated Code

DSA Rust

fn merge_sort(arr: &mut [i32]) {
    let len = arr.len();
    if len <= 1 {
        return; // base case: array is already sorted
    }
    let mid = len / 2;
    merge_sort(&mut arr[..mid]); // sort left half
    merge_sort(&mut arr[mid..]); // sort right half

    // merge two sorted halves
    let mut merged = Vec::with_capacity(len);
    let (mut left, mut right) = (0, mid);

    while left < mid && right < len {
        if arr[left] <= arr[right] {
            merged.push(arr[left]);
            left += 1; // advance left pointer
        } else {
            merged.push(arr[right]);
            right += 1; // advance right pointer
        }
    }

    // append remaining elements from left half
    while left < mid {
        merged.push(arr[left]);
        left += 1; // add leftover left elements
    }

    // append remaining elements from right half
    while right < len {
        merged.push(arr[right]);
        right += 1; // add leftover right elements
    }

    // copy merged back to original array
    arr.copy_from_slice(&merged);
}

fn main() {
    let mut data = vec![38, 27, 43, 3, 9, 82, 10];
    merge_sort(&mut data);
    println!("{:?}", data);
}

if len <= 1 { return; }

stop recursion when array has 1 or 0 elements

merge_sort(&mut arr[..mid]);

recursively sort left half

merge_sort(&mut arr[mid..]);

recursively sort right half

while left < mid && right < len { ... }

merge elements from left and right halves in order

while left < mid { ... }

append remaining elements from left half

while right < len { ... }

append remaining elements from right half

arr.copy_from_slice(&merged);

copy merged sorted elements back to original array

Output

[3, 9, 10, 27, 38, 43, 82]

Complexity Analysis

Time: O(n log n) because the list is repeatedly split in half (log n splits) and merging takes linear time at each level

Space: O(n) because extra space is needed to store merged arrays during merging

vs Alternative: Compared to simple sorting like bubble sort (O(n^2)), merge sort is much faster for large lists due to divide and conquer approach

Edge Cases

empty list

function returns immediately without changes

DSA Rust

if len <= 1 { return; }

single element list

function returns immediately as list is already sorted

DSA Rust

if len <= 1 { return; }

list with duplicate elements

duplicates are kept and sorted correctly

DSA Rust

while left < mid && right < len { ... }

When to Use This Pattern

When you see a problem asking to sort or organize data efficiently, especially large lists, reach for merge sort because it splits the problem into smaller parts and merges them back sorted.

Common Mistakes

Mistake: Not copying merged array back to original array after merging
Fix: Add arr.copy_from_slice(&merged) to update original array with sorted elements

Mistake: Not handling base case when array length is 1 or 0, causing infinite recursion
Fix: Add base case check if len <= 1 { return; } to stop recursion

Mistake: Merging without checking bounds, causing index out of range errors
Fix: Use while loops with proper boundary checks for left and right pointers

Summary

It sorts a list by splitting it into smaller parts, sorting those, and merging them back.

Use it when you want a reliable, efficient sorting method especially for large lists.

The key insight is breaking the problem into smaller sorted pieces and combining them carefully.

Practice

1. What is the main idea behind the Merge Sort algorithm in the context of divide and conquer?

easy

A. Select a pivot and partition the array around it

B. Sort the array by swapping adjacent elements repeatedly

C. Build a heap and extract elements in sorted order

D. Divide the array into halves, sort each half, then merge them

Solution

1. Step 1: Understand divide and conquer in Merge Sort

   Merge Sort splits the array into two halves recursively until single elements remain.

2. Step 2: Merge sorted halves

   After splitting, it merges the sorted halves back together to form a sorted array.

3. Final Answer:

   Divide the array into halves, sort each half, then merge them -> Option D

4. Quick Check:

   Divide and conquer = split, sort, merge [OK]

Hint: Remember: split, sort, then merge halves [OK]

Common Mistakes:

• Confusing Merge Sort with Bubble Sort
• Thinking Merge Sort uses a pivot like Quick Sort
• Ignoring the merge step after dividing

2. Which of the following is the correct Rust function signature for a merge sort function that sorts a mutable slice of integers?

easy

A. fn merge_sort(arr: Vec<i32>) -> Vec<i32>

B. fn merge_sort(arr: &mut [i32])

C. fn merge_sort(arr: &[i32]) -> &[i32]

D. fn merge_sort(arr: &mut Vec<i32>) -> ()

Solution

1. Step 1: Identify mutable slice parameter

   Merge sort modifies the array in place, so it needs a mutable slice: &mut [i32].

2. Step 2: Check function return type

   In-place sorting returns nothing, so return type is omitted (unit type).

3. Final Answer:

   fn merge_sort(arr: &mut [i32]) -> Option B

4. Quick Check:

   Mutable slice input, no return [OK]

Hint: Use &mut [i32] for in-place sorting in Rust [OK]

Common Mistakes:

• Using immutable slice &[i32] when mutation is needed
• Returning a new vector instead of sorting in place
• Incorrect return type for in-place function

3. What will be the output of the following Rust code snippet using merge sort on the array [4, 1, 3, 2]?

fn main() {
    let mut arr = [4, 1, 3, 2];
    merge_sort(&mut arr);
    println!("{:?}", arr);
}

fn merge_sort(arr: &mut [i32]) {
    let mid = arr.len() / 2;
    if mid == 0 { return; }
    merge_sort(&mut arr[..mid]);
    merge_sort(&mut arr[mid..]);
    let mut merged = arr.to_vec();
    merge(&arr[..mid], &arr[mid..], &mut merged[..]);
    arr.copy_from_slice(&merged);
}

fn merge(left: &[i32], right: &[i32], merged: &mut [i32]) {
    let mut i = 0;
    let mut j = 0;
    let mut k = 0;
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            merged[k] = left[i];
            i += 1;
        } else {
            merged[k] = right[j];
            j += 1;
        }
        k += 1;
    }
    while i < left.len() {
        merged[k] = left[i];
        i += 1;
        k += 1;
    }
    while j < right.len() {
        merged[k] = right[j];
        j += 1;
        k += 1;
    }
}

medium

A. [1, 2, 3, 4]

B. [4, 3, 2, 1]

C. [1, 3, 2, 4]

D. [2, 1, 3, 4]

Solution

1. Step 1: Trace recursive splitting

   Array splits into [4,1] and [3,2], then further into single elements.

2. Step 2: Merge sorted halves

   Merge [4] and [1] into [1,4], merge [3] and [2] into [2,3], then merge [1,4] and [2,3] into [1,2,3,4].

3. Final Answer:

   [1, 2, 3, 4] -> Option A

4. Quick Check:

   Sorted array = [1, 2, 3, 4] [OK]

Hint: Merge halves step-by-step to get sorted array [OK]

Common Mistakes:

• Confusing merge order causing wrong output
• Forgetting to copy merged array back
• Incorrect base case stopping recursion too early

4. Identify the bug in this Rust merge sort implementation snippet:

fn merge_sort(arr: &mut [i32]) {
    let mid = arr.len() / 2;
    if arr.len() <= 1 { return; }
    merge_sort(&mut arr[..mid]);
    merge_sort(&mut arr[mid..]);
    let mut merged = arr.to_vec();
    merge(&arr[..mid], &arr[mid..], &mut merged[..]);
    arr.copy_from_slice(&merged);
}

medium

A. The base case condition is correct; no bug here

B. The slices passed to merge overlap and cause incorrect merging

C. The merge function is called with immutable slices, but merged is mutable

D. The base case condition should check if mid == 0, not arr.len() <= 1

Solution

1. Step 1: Check base case

   The condition if arr.len() <= 1 { return; } correctly handles arrays of length 0 or 1.

2. Step 2: Verify recursive calls

   Disjoint mutable slices arr[..mid] and arr[mid..] are sorted independently.

3. Step 3: Examine merge

   Immutable borrows of disjoint slices to merge are temporary; writes to separate merged vec. No overlap or borrow issues.

4. Final Answer:

   The base case condition is correct; no bug here -> Option A

5. Quick Check:

   Disjoint slices + temporary borrows = safe [OK]

Hint: Verify disjoint slices and borrow lifetimes; this is correct [OK]

Common Mistakes:

• Ignoring slice borrowing rules in Rust
• Confusing base case condition with bug
• Assuming immutable slices cause errors with mutable writes

5. Given a large array of integers with many duplicate values, how can you modify the merge step in merge sort to optimize performance by reducing unnecessary copying?

hard

A. Skip copying elements when both halves have equal values during merge

B. Avoid merging duplicates by sorting only unique elements

C. Use a stable merge that avoids copying duplicates by referencing indices

D. Count duplicates and merge them as a single element to reduce size

Solution

1. Step 1: Understand stable merge importance

   Stable merge preserves order of equal elements and can optimize by referencing indices instead of copying repeatedly.

2. Step 2: Avoid unnecessary copying of duplicates

   By using indices and stable merge logic, duplicates are merged efficiently without extra copying.

3. Final Answer:

   Use a stable merge that avoids copying duplicates by referencing indices -> Option C

4. Quick Check:

   Stable merge optimizes duplicate handling [OK]

Hint: Use stable merge to handle duplicates efficiently [OK]

Common Mistakes:

• Trying to merge duplicates as single element (loses data)
• Skipping copying equal elements breaks stability
• Sorting only unique elements changes array content