Merge Sort Algorithm 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 them into small piles, sorting each small pile, then carefully combining the piles back into one sorted stack.

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

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

Each half split further until single elements:
[38] [27] [43] -> [3] [9] [82] [10]

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] and [3, 9, 82, 10]

Why: We break the problem into smaller parts to sort easily

Step 2: Split first half into [38] and [27, 43]

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

Why: Keep splitting until parts have one element

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

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

Why: Single elements are considered sorted

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

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

Why: Combine small sorted parts into bigger sorted parts

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

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

Why: Continue merging sorted parts

Step 6: Split second half into [3, 9] and [82, 10]

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

Why: Split second half to sort smaller parts

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

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

Why: Single elements are sorted

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

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

Why: Merge small sorted parts

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

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

Why: Split until single elements

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

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

Why: Merge sorted parts

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

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

Why: Merge bigger sorted parts

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

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

Why: Final merge gives fully 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: single element is sorted
    }
    let mid = len / 2;
    merge_sort(&mut arr[..mid]); // sort left half
    merge_sort(&mut arr[mid..]); // sort right half
    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 = 0; // index for left
    let mut j = 0; // index for right
    let mut k = 0; // index for merged arr

    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            arr[k] = left[i];
            i += 1; // take from left
        } else {
            arr[k] = right[j];
            j += 1; // take from right
        }
        k += 1; // move merged index
    }

    while i < left.len() {
        arr[k] = left[i];
        i += 1; // copy remaining left
        k += 1;
    }

    while j < right.len() {
        arr[k] = right[j];
        j += 1; // copy remaining right
        k += 1;
    }
}

fn main() {
    let mut arr = vec![38, 27, 43, 3, 9, 82, 10];
    merge_sort(&mut arr);
    for num in arr {
        print!("{} ", num);
    }
    println!();
}

if len <= 1 { return; }

stop splitting when part has one or zero elements

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

recursively sort left half

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

recursively sort right half

merge(arr, mid);

merge two sorted halves into one sorted array

while i < left.len() && j < right.len() { ... }

compare elements from left and right, pick smaller to merged array

while i < left.len() { ... }

copy remaining elements from left if any

while j < right.len() { ... }

copy remaining elements from right if any

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 hold temporary arrays during merging

vs Alternative: Compared to simple sorting like bubble sort O(n²), merge sort is much faster for large lists but uses extra memory

Edge Cases

empty list

function returns immediately without changes

DSA Rust

if len <= 1 { return; }

single element list

considered sorted, no further action

DSA Rust

if len <= 1 { return; }

list with duplicate elements

duplicates are kept and sorted correctly

DSA Rust

if left[i] <= right[j] { arr[k] = left[i]; i += 1; } else { arr[k] = right[j]; j += 1; }

When to Use This Pattern

When you need to sort a list efficiently and can use extra space, reach for merge sort because it guarantees O(n log n) time by dividing and conquering.

Common Mistakes

Mistake: Not copying remaining elements after one side is exhausted during merge
Fix: Add loops to copy leftover elements from left and right arrays after main comparison loop

Mistake: Modifying the original array before sorting both halves
Fix: Always sort both halves recursively before merging

Summary

It sorts a list by splitting it into halves, sorting each half, then merging them back in order.

Use it when you want a reliable, efficient sorting method that works well on large lists.

The key insight is breaking the problem into smaller sorted parts and merging them carefully.

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