Merge Sort Algorithm in DSA Rust - Execution Trace

Concept Flow - Merge Sort Algorithm

Start with full array

↓

Divide array into two halves

↓

Recursively apply merge sort on left half

↓

Base case: single element or empty array

↓

Merge two sorted halves

↓

Sorted array

Merge Sort splits the array into halves recursively until single elements remain, then merges sorted halves back together.

Execution Sample

DSA Rust

fn merge(arr: &mut [i32], mid: usize) {
    let mut temp = vec![0i32; arr.len()];
    let mut i = 0;
    let mut j = mid;
    let mut k = 0;
    while i < mid && j < arr.len() {
        if arr[i] <= arr[j] {
            temp[k] = arr[i];
            i += 1;
        } else {
            temp[k] = arr[j];
            j += 1;
        }
        k += 1;
    }
    while i < mid {
        temp[k] = arr[i];
        i += 1;
        k += 1;
    }
    while j < arr.len() {
        temp[k] = arr[j];
        j += 1;
        k += 1;
    }
    for (idx, &val) in temp.iter().enumerate() {
        arr[idx] = val;
    }
}

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

This code recursively splits the array and merges sorted halves to sort the entire array.

Execution Table

Step	Operation	Array Segment	Action Detail	Array State
1	Start	[38, 27, 43, 3, 9, 82, 10]	Full array to sort	[38, 27, 43, 3, 9, 82, 10]
2	Divide	[38, 27, 43, 3, 9, 82, 10]	Split into [38,27,43] and [3,9,82,10]	[38, 27, 43, 3, 9, 82, 10]
3	Divide Left	[38, 27, 43]	Split into [38] and [27,43]	[38, 27, 43, 3, 9, 82, 10]
4	Base Case	[38]	Single element, no sort	[38, 27, 43, 3, 9, 82, 10]
5	Divide Right Left	[27, 43]	Split into [27] and [43]	[38, 27, 43, 3, 9, 82, 10]
6	Base Case	[27]	Single element, no sort	[38, 27, 43, 3, 9, 82, 10]
7	Base Case	[43]	Single element, no sort	[38, 27, 43, 3, 9, 82, 10]
8	Merge	[27, 43]	Merge [27] and [43]	[38, 27, 43, 3, 9, 82, 10]
9	Merge	[38, 27, 43]	Merge [38] and [27,43]	[27, 38, 43, 3, 9, 82, 10]
10	Divide Right	[3, 9, 82, 10]	Split into [3,9] and [82,10]	[27, 38, 43, 3, 9, 82, 10]
11	Divide Right Left	[3, 9]	Split into [3] and [9]	[27, 38, 43, 3, 9, 82, 10]
12	Base Case	[3]	Single element, no sort	[27, 38, 43, 3, 9, 82, 10]
13	Base Case	[9]	Single element, no sort	[27, 38, 43, 3, 9, 82, 10]
14	Merge	[3, 9]	Merge [3] and [9]	[27, 38, 43, 3, 9, 82, 10]
15	Divide Right Right	[82, 10]	Split into [82] and [10]	[27, 38, 43, 3, 9, 82, 10]
16	Base Case	[82]	Single element, no sort	[27, 38, 43, 3, 9, 82, 10]
17	Base Case	[10]	Single element, no sort	[27, 38, 43, 3, 9, 82, 10]
18	Merge	[82, 10]	Merge [82] and [10]	[27, 38, 43, 3, 9, 10, 82]
19	Merge	[3, 9, 10, 82]	Merge [3,9] and [10,82]	[27, 38, 43, 3, 9, 10, 82]
20	Merge	[27, 38, 43, 3, 9, 10, 82]	Merge [27,38,43] and [3,9,10,82]	[3, 9, 10, 27, 38, 43, 82]
21	End	[3, 9, 10, 27, 38, 43, 82]	Array fully sorted	[3, 9, 10, 27, 38, 43, 82]

💡 All subarrays reduced to single elements and merged back fully sorted

Variable Tracker

Variable	Start	After Step 9	After Step 14	After Step 19	Final
Array	[38, 27, 43, 3, 9, 82, 10]	[27, 38, 43, 3, 9, 82, 10]	[27, 38, 43, 3, 9, 82, 10]	[27, 38, 43, 3, 9, 10, 82]	[3, 9, 10, 27, 38, 43, 82]
Left Half	[38, 27, 43]	[27, 38, 43]	[27, 38, 43]	[27, 38, 43]	[27, 38, 43]
Right Half	[3, 9, 82, 10]	[3, 9, 82, 10]	[3, 9, 82, 10]	[3, 9, 10, 82]	[3, 9, 10, 82]

Key Moments - 3 Insights

Why do we stop dividing when the array segment has only one element?

Because a single element is already sorted, so no further division or sorting is needed. See execution_table rows 4, 6, 7, 12, 13, 16, 17 where base cases occur.

How does merging two sorted halves produce a fully sorted array?

Merging compares elements from both halves and picks the smaller one step-by-step, preserving order. This is shown in execution_table rows 8, 9, 14, 18, 19, and 20 where merges happen.

Why do we need to recursively sort both halves before merging?

Because merging only works correctly if both halves are already sorted. The recursion ensures this by sorting smaller parts first, as seen in the divide and base case steps before merges.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the array state after merging the left half?

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

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

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

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

💡 Hint

Check the 'Array State' column at step 9 in execution_table

At which step does the right half [3, 9, 82, 10] get fully merged and sorted?

A Step 14

B Step 20

C Step 19

D Step 18

💡 Hint

Look for the merge operation on the right half in execution_table rows 19 and 20

If the initial array was already sorted, how would the merge steps change?

A Merges would still happen but no swaps needed

B No merges would happen

C The array would be reversed

D The recursion would stop immediately

💡 Hint

Merging always happens after dividing, but if sorted, elements are picked without swaps

Concept Snapshot

Merge Sort Algorithm:
- Recursively split array into halves until single elements
- Merge sorted halves by comparing elements
- Time complexity: O(n log n)
- Stable and works well for large data
- Uses extra space for merging
- Divide and conquer approach

Full Transcript

Merge Sort Algorithm splits the array into two halves recursively until each segment has one element, which is inherently sorted. Then it merges these sorted halves step-by-step by comparing elements from each half, building up a fully sorted array. The process involves dividing, base case checks, and merging. The execution table shows each step with array segments and their states. Key moments clarify why single elements are base cases, how merging works, and why sorting both halves before merging is necessary. The visual quiz tests understanding of array states at merge steps and behavior if the array is already sorted. Merge Sort is a stable, efficient sorting method using divide and conquer.

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