Merge Sort as Divide and Conquer in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Merge Sort on a small array

What is the output of the following Rust code after sorting the array using merge sort?

DSA Rust

fn merge_sort(mut arr: Vec<i32>) -> Vec<i32> {
    if arr.len() <= 1 {
        return arr;
    }
    let mid = arr.len() / 2;
    let left = merge_sort(arr[..mid].to_vec());
    let right = merge_sort(arr[mid..].to_vec());
    merge(left, right)
}

fn merge(left: Vec<i32>, right: Vec<i32>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut i = 0;
    let mut j = 0;
    while i < left.len() && j < right.len() {
        if left[i] < right[j] {
            result.push(left[i]);
            i += 1;
        } else {
            result.push(right[j]);
            j += 1;
        }
    }
    while i < left.len() {
        result.push(left[i]);
        i += 1;
    }
    while j < right.len() {
        result.push(right[j]);
        j += 1;
    }
    result
}

fn main() {
    let arr = vec![3, 1, 4, 1, 5];
    let sorted = merge_sort(arr);
    println!("{:?}", sorted);
}

A [5, 4, 3, 1, 1]

B [1, 3, 4, 1, 5]

C [3, 1, 4, 1, 5]

D [1, 1, 3, 4, 5]

💡 Hint

Think about how merge sort splits and merges arrays in sorted order.

Merge sort splits the array into halves recursively and merges them back in sorted order. The final output is the sorted array.

❓ Predict Output

intermediate

Result of merging two sorted vectors

What is the output of merging these two sorted vectors using the merge function?

DSA Rust

fn merge(left: Vec<i32>, right: Vec<i32>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut i = 0;
    let mut j = 0;
    while i < left.len() && j < right.len() {
        if left[i] < right[j] {
            result.push(left[i]);
            i += 1;
        } else {
            result.push(right[j]);
            j += 1;
        }
    }
    while i < left.len() {
        result.push(left[i]);
        i += 1;
    }
    while j < right.len() {
        result.push(right[j]);
        j += 1;
    }
    result
}

fn main() {
    let left = vec![2, 4, 6];
    let right = vec![1, 3, 5];
    let merged = merge(left, right);
    println!("{:?}", merged);
}

A [2, 4, 6, 1, 3, 5]

B [1, 3, 5, 2, 4, 6]

C [1, 2, 3, 4, 5, 6]

D [6, 5, 4, 3, 2, 1]

💡 Hint

Merging two sorted lists results in a sorted combined list.

The merge function compares elements from both lists and appends the smaller one, resulting in a fully sorted merged list.

🔧 Debug

advanced

Identify the bug in this merge sort implementation

What error will this Rust code produce when running the merge_sort function?

DSA Rust

fn merge_sort(arr: Vec<i32>) -> Vec<i32> {
    if arr.len() <= 1 {
        return arr;
    }
    let mid = arr.len() / 2;
    let left = merge_sort(arr[..mid].to_vec());
    let right = merge_sort(arr[mid..].to_vec());
    merge(left, right)
}

fn merge(left: Vec<i32>, right: Vec<i32>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut i = 0;
    let mut j = 0;
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            result.push(left[i]);
            i += 1;
        } else {
            result.push(right[j]);
            j += 1;
        }
    }
    while i < left.len() {
        result.push(left[i]);
        i += 1;
    }
    while j < right.len() {
        result.push(right[j]);
        j += 1;
    }
    result
}

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

A Runtime panic due to index out of bounds

B No error, outputs [1, 2, 3]

C Compilation error due to borrowing issues

D Outputs [3, 2, 1] without sorting

💡 Hint

Check if the slicing and merging logic is correct and safe.

The code correctly slices the vector and merges sorted halves without errors, producing sorted output.

❓ Predict Output

advanced

Output of merge sort on an empty vector

What is the output of the merge_sort function when given an empty vector?

DSA Rust

fn merge_sort(arr: Vec<i32>) -> Vec<i32> {
    if arr.len() <= 1 {
        return arr;
    }
    let mid = arr.len() / 2;
    let left = merge_sort(arr[..mid].to_vec());
    let right = merge_sort(arr[mid..].to_vec());
    merge(left, right)
}

fn merge(left: Vec<i32>, right: Vec<i32>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut i = 0;
    let mut j = 0;
    while i < left.len() && j < right.len() {
        if left[i] < right[j] {
            result.push(left[i]);
            i += 1;
        } else {
            result.push(right[j]);
            j += 1;
        }
    }
    while i < left.len() {
        result.push(left[i]);
        i += 1;
    }
    while j < right.len() {
        result.push(right[j]);
        j += 1;
    }
    result
}

fn main() {
    let arr: Vec<i32> = vec![];
    let sorted = merge_sort(arr);
    println!("{:?}", sorted);
}

A []

B [0]

C Compilation error

D Runtime panic

💡 Hint

Consider the base case for empty or single-element vectors.

The base case returns the vector as is if its length is 0 or 1, so an empty vector returns empty.

🚀 Application

expert

Number of recursive calls in merge sort

Given an input vector of length 8, how many total calls to merge_sort (including the initial call) will be made during the full sorting process?

A 15

B 8

C 7

D 16

💡 Hint

Think about how merge sort splits the array into halves recursively until single elements.

Merge sort calls merge_sort once per subarray. For length 8, it splits into 8 single elements, resulting in 15 calls total (2*n - 1).

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