Merge Sort Algorithm in DSA Rust - Time & Space Complexity

Time Complexity: Merge Sort Algorithm

O(n log n)

Understanding Time Complexity

We want to understand how the time taken by merge sort changes as the list size grows.

How does the number of steps grow when sorting bigger lists?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

fn merge(arr: &mut [i32], mid: usize) {
    let left = arr[..mid].to_vec();
    let right = arr[mid..].to_vec();
    let (mut i, mut j, mut k) = (0, 0, 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;
    }
}

This code splits the list into halves recursively, then merges sorted halves back together.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursively splitting the array and merging sorted halves.
• How many times: The array is split about log₂(n) times, and merging happens at each level over all elements.

How Execution Grows With Input

Each split halves the list, creating about log₂(n) levels of splitting.

At each level, merging all parts touches every element once.

Input Size (n)	Approx. Operations
10	About 10 x 4 = 40
100	About 100 x 7 = 700
1000	About 1000 x 10 = 10,000

Pattern observation: Operations grow roughly as n times log n, which grows faster than n but much slower than n squared.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit more than linearly but much less than quadratic as the list size increases.

Common Mistake

[X] Wrong: "Merge sort is as slow as bubble sort because both compare elements repeatedly."

[OK] Correct: Merge sort smartly splits and merges, doing fewer total comparisons, so it runs much faster on large lists.

Interview Connect

Understanding merge sort's time complexity shows you can analyze recursive algorithms and their efficiency, a key skill in many coding challenges.

Self-Check

"What if we changed merge sort to split the array into three parts instead of two? How would the time complexity change?"

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