Merge Sort Algorithm 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 that uses merge sort on the array [4, 1, 3, 2]?

DSA Rust

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 ret = arr.to_vec();
    merge(&arr[..mid], &arr[mid..], &mut ret[..]);
    arr.copy_from_slice(&ret);
}

fn merge(left: &[i32], right: &[i32], ret: &mut [i32]) {
    let mut left_i = 0;
    let mut right_i = 0;
    let mut ret_i = 0;
    while left_i < left.len() && right_i < right.len() {
        if left[left_i] <= right[right_i] {
            ret[ret_i] = left[left_i];
            left_i += 1;
        } else {
            ret[ret_i] = right[right_i];
            right_i += 1;
        }
        ret_i += 1;
    }
    while left_i < left.len() {
        ret[ret_i] = left[left_i];
        left_i += 1;
        ret_i += 1;
    }
    while right_i < right.len() {
        ret[ret_i] = right[right_i];
        right_i += 1;
        ret_i += 1;
    }
}

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

A [1, 2, 3, 4]

B [4, 3, 2, 1]

C [1, 3, 2, 4]

D [2, 1, 3, 4]

💡 Hint

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

Merge sort divides the array into halves recursively and merges them back in sorted order. The final sorted array is [1, 2, 3, 4].

🧠 Conceptual

intermediate

Time complexity of Merge Sort

What is the time complexity of the merge sort algorithm in the average and worst cases?

A O(log n)

B O(n^2)

C O(n log n)

D O(n)

💡 Hint

Consider how many times the array is divided and merged.

Merge sort divides the array into halves (log n times) and merges all elements (n) each time, resulting in O(n log n) time complexity.

🔧 Debug

advanced

Identify the bug in this merge function

What error will occur when running this merge function in Rust?

DSA Rust

fn merge(left: &[i32], right: &[i32], ret: &mut [i32]) {
    let mut left_i = 0;
    let mut right_i = 0;
    let mut ret_i = 0;
    while left_i < left.len() && right_i < right.len() {
        if left[left_i] < right[right_i] {
            ret[ret_i] = left[left_i];
            left_i += 1;
        } else {
            ret[ret_i] = right[right_i];
            right_i += 1;
        }
        ret_i += 1;
    }
    while left_i < left.len() {
        ret[ret_i] = left[left_i];
        left_i += 1;
        ret_i += 1;
    }
    while right_i < right.len() {
        ret[ret_i] = right[right_i];
        right_i += 1;
        ret_i += 1;
    }
}

A Infinite loop because ret_i is never incremented

B No error, function works correctly

C Type mismatch error due to wrong slice type

D Index out of bounds panic due to incorrect loop condition

💡 Hint

Check the loop conditions carefully for off-by-one errors.

The loop 'while left_i <= left.len()' allows left_i to equal left.len(), causing an index out of bounds panic when accessing left[left_i].

📝 Syntax

advanced

Correct Rust syntax for merge sort recursive call

Which option correctly calls merge_sort recursively on the left half of the array slice in Rust?

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

B merge_sort(arr[0..mid]);

C merge_sort(&arr[0..mid]);

D merge_sort(arr[..mid]);

💡 Hint

Remember Rust requires mutable references for modifying slices.

Option A passes a mutable reference to the left half slice, which is required for in-place sorting. Options A and D lack references, and C is an immutable reference.

🚀 Application

expert

Number of merge operations in merge sort

For an array of length 8, how many total merge operations does merge sort perform during the entire sorting process?

A 15

B 7

C 8

D 16

💡 Hint

Think about how many times the array is split and merged back.

Merge sort splits the array into single elements and merges pairs back. For 8 elements, it performs 7 merges (one less than the number of elements).

Practice

1. What is the main idea behind the Merge Sort Algorithm?

easy

A. Divide the list into halves, sort each half, then merge them

B. Sort the list by repeatedly swapping adjacent elements

C. Pick a pivot and partition the list around it

D. Insert elements one by one into a sorted list

Solution

1. Step 1: Understand the divide and conquer approach

   Merge sort splits the list into smaller parts to make sorting easier.

2. Step 2: Merge sorted halves

   After sorting each half, it merges them to form a fully sorted list.

3. Final Answer:

   Divide the list into halves, sort each half, then merge them -> Option A

4. Quick Check:

   Merge Sort = Divide, Sort halves, Merge [OK]

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

Common Mistakes:

• Confusing merge sort with bubble sort
• Thinking merge sort sorts in place without merging
• Mixing merge sort with quicksort partitioning

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

easy

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

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

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

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

Solution

1. Step 1: Understand ownership and mutability in Rust

   To sort in place, the function needs a mutable reference to the vector.

2. Step 2: Check function signature options

   fn merge_sort(arr: &mut Vec<i32>) takes a mutable reference, allowing in-place sorting without ownership transfer.

3. Final Answer:

   fn merge_sort(arr: &mut Vec<i32>) -> Option C

4. Quick Check:

   Mutable reference needed for in-place sort [OK]

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

Common Mistakes:

• Using owned Vec without returning sorted vector
• Using immutable reference when mutation is needed
• Missing return type when function returns new vector

3. What will be the output of the following Rust code snippet using merge sort?

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

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

fn merge(arr: &mut Vec<i32>, left: &Vec<i32>, right: &Vec<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] {
            arr[k] = left[i];
            i += 1;
        } else {
            arr[k] = right[j];
            j += 1;
        }
        k += 1;
    }
    while i < left.len() {
        arr[k] = left[i];
        i += 1;
        k += 1;
    }
    while j < right.len() {
        arr[k] = right[j];
        j += 1;
        k += 1;
    }
}

medium

A. [2, 1, 3, 4]

B. [1, 2, 3, 4]

C. [1, 3, 2, 4]

D. [4, 3, 2, 1]

Solution

1. Step 1: Trace the recursive splitting

   The array [4,1,3,2] is split into [4,1] and [3,2], then further split until single elements.

2. Step 2: Merge sorted halves

   Single elements are merged back in sorted order: [1,4] and [2,3], then merged to [1,2,3,4].

3. Final Answer:

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

4. Quick Check:

   Merge sort output = sorted array ascending [OK]

Hint: Merge sort always outputs sorted ascending list [OK]

Common Mistakes:

• Confusing merge order and output
• Forgetting to copy back merged elements
• Mixing up indices during merge

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

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

fn merge(arr: &mut Vec<i32>, left: &Vec<i32>, right: &Vec<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] {
            arr[k] = left[i];
            i += 1;
        } else {
            arr[k] = right[j];
            j += 1;
        }
        k += 1;
    }
    while i < left.len() {
        arr[k] = left[i];
        i += 1;
        k += 1;
    }
    while j < right.len() {
        arr[k] = right[j];
        j += 1;
        k += 1;
    }
}

medium

A. The merge condition should use <= instead of < to maintain stability

B. The function should return a new vector instead of modifying in place

C. The mid index calculation is incorrect and causes panic

D. The merge function does not handle empty vectors

Solution

1. Step 1: Analyze the merge comparison condition

   The condition uses < which can reorder equal elements, breaking stability.

2. Step 2: Correct the condition for stable sort

   Using <= ensures equal elements keep their original order, preserving stability.

3. Final Answer:

   The merge condition should use <= instead of < to maintain stability -> Option A

4. Quick Check:

   Use <= in merge to keep stable order [OK]

Hint: Use <= in merge to keep equal elements stable [OK]

Common Mistakes:

• Ignoring stability in merge condition
• Thinking mid calculation causes error
• Assuming merge must return new vector

5. Given a large vector of integers with many duplicate values, how can you modify the merge sort algorithm in Rust to efficiently sort and remove duplicates during the merge step?

hard

A. Sort normally then use a separate pass to remove duplicates after merge sort completes

B. Change merge sort to quicksort for better duplicate handling

C. Use a HashSet to store elements during merge and convert back to vector

D. Modify the merge function to skip adding duplicates when merging sorted halves

Solution

1. Step 1: Understand duplicate removal during merge

   While merging, compare current elements and skip adding if equal to last added element.

2. Step 2: Implement skipping duplicates in merge

   This avoids extra passes and keeps sorting efficient by removing duplicates on the fly.

3. Final Answer:

   Modify the merge function to skip adding duplicates when merging sorted halves -> Option D

4. Quick Check:

   Skip duplicates during merge for efficient unique sort [OK]

Hint: Skip duplicates while merging to avoid extra passes [OK]

Common Mistakes:

• Removing duplicates only after full sort wastes time
• Using HashSet breaks order and adds overhead
• Switching to quicksort doesn't inherently remove duplicates