Merge Sort

Merge sort is a divide-and-conquer algorithm that guarantees O(n log n) time complexity in all cases. It works by recursively dividing the array in half, sorting each half, and merging the sorted halves back together.

The Divide and Conquer Strategy

1. Divide: Split the array into two halves
2. Conquer: Recursively sort each half
3. Combine: Merge the sorted halves into one sorted array

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

Divide Phase:
                [38, 27, 43, 3, 9, 82, 10]
                       /            \
              [38, 27, 43, 3]    [9, 82, 10]
                /       \           /     \
           [38, 27]  [43, 3]    [9, 82]  [10]
            /   \     /   \      /   \      |
          [38] [27] [43] [3]   [9] [82]   [10]

Merge Phase:
          [38] [27] [43] [3]   [9] [82]   [10]
            \   /     \   /      \   /      |
           [27, 38]  [3, 43]    [9, 82]   [10]
                \       /           \     /
              [3, 27, 38, 43]    [9, 10, 82]
                       \            /
                [3, 9, 10, 27, 38, 43, 82]

The Merge Operation

The key insight is that merging two sorted arrays takes O(n) time:

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

Left:  [3, 27, 38, 43]    Right: [9, 10, 82]    Result: []
        ↑                          ↑

Compare 3 vs 9: 3 < 9, take 3
Left:  [3, 27, 38, 43]    Right: [9, 10, 82]    Result: [3]
           ↑                       ↑

Compare 27 vs 9: 9 < 27, take 9
Left:  [3, 27, 38, 43]    Right: [9, 10, 82]    Result: [3, 9]
           ↑                          ↑

Compare 27 vs 10: 10 < 27, take 10
Left:  [3, 27, 38, 43]    Right: [9, 10, 82]    Result: [3, 9, 10]
           ↑                              ↑

Compare 27 vs 82: 27 < 82, take 27
...continue until done...

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

Implementation

fn merge_sort(arr: Vec<i32>) -> Vec<i32> {
    // Base case: single element is already sorted
    if arr.len() <= 1 {
        return arr;
    }

    // Divide
    let mid = arr.len() / 2;
    let left = merge_sort(arr[..mid].to_vec());
    let right = merge_sort(arr[mid..].to_vec());

    // Combine
    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;

    // Merge while both arrays have elements
    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;
        }
    }

    // Append remaining elements
    result.extend_from_slice(&left[i..]);
    result.extend_from_slice(&right[j..]);

    result
}

fn main() {
    let arr = vec![38, 27, 43, 3, 9, 82, 10];
    let sorted = merge_sort(arr);
    println!("{:?}", sorted);
    // [3, 9, 10, 27, 38, 43, 82]
}

In-Place Merge Sort

The standard merge sort uses O(n) extra space. Here's an in-place version:

fn merge_sort_inplace(arr: &mut [i32]) {
    let len = arr.len();
    if len <= 1 {
        return;
    }

    let mid = len / 2;
    merge_sort_inplace(&mut arr[..mid]);
    merge_sort_inplace(&mut arr[mid..]);
    merge_inplace(arr, mid);
}

fn merge_inplace(arr: &mut [i32], mid: usize) {
    // Create temp arrays
    let left = arr[..mid].to_vec();
    let right = arr[mid..].to_vec();

    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;
    }
}

fn main() {
    let mut arr = vec![38, 27, 43, 3, 9, 82, 10];
    merge_sort_inplace(&mut arr);
    println!("{:?}", arr);
}

Time Complexity Analysis

The recurrence relation is:

T(n) = 2T(n/2) + O(n)

- 2T(n/2): Two recursive calls on half-size arrays
- O(n): Linear merge operation

Solution: O(n log n)

Level 0:            n                    (1 array of size n)
Level 1:       n/2     n/2               (2 arrays of size n/2)
Level 2:    n/4   n/4   n/4   n/4        (4 arrays of size n/4)
...
Level log n:  1  1  1  1  1  1  1  1     (n arrays of size 1)

Each level does O(n) work (merging)
Number of levels: log n
Total: O(n log n)

Space Complexity

• Standard merge sort: O(n) for temporary arrays during merge
• Call stack: O(log n) for recursion depth
• Total: O(n)

Properties

| Property | Merge Sort | |----------|------------| | Time (all cases) | O(n log n) | | Space | O(n) | | Stable | Yes | | In-place | No | | Adaptive | No |

Bottom-Up Merge Sort

Iterative version that avoids recursion:

fn merge_sort_bottom_up(arr: &mut [i32]) {
    let n = arr.len();
    let mut width = 1;

    while width < n {
        let mut i = 0;
        while i < n {
            let left = i;
            let mid = std::cmp::min(i + width, n);
            let right = std::cmp::min(i + 2 * width, n);

            if mid < right {
                merge_section(arr, left, mid, right);
            }

            i += 2 * width;
        }

        width *= 2;
    }
}

fn merge_section(arr: &mut [i32], left: usize, mid: usize, right: usize) {
    let left_arr = arr[left..mid].to_vec();
    let right_arr = arr[mid..right].to_vec();

    let mut i = 0;
    let mut j = 0;
    let mut k = left;

    while i < left_arr.len() && j < right_arr.len() {
        if left_arr[i] <= right_arr[j] {
            arr[k] = left_arr[i];
            i += 1;
        } else {
            arr[k] = right_arr[j];
            j += 1;
        }
        k += 1;
    }

    while i < left_arr.len() {
        arr[k] = left_arr[i];
        i += 1;
        k += 1;
    }

    while j < right_arr.len() {
        arr[k] = right_arr[j];
        j += 1;
        k += 1;
    }
}

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

Bottom-up process for [4, 3, 2, 1]:

Width 1: Merge pairs of 1
[4, 3, 2, 1] → [3, 4, 1, 2]

Width 2: Merge pairs of 2
[3, 4, 1, 2] → [1, 2, 3, 4]

Done!

Merge Sort for Linked Lists

Merge sort is ideal for linked lists (O(log n) space for merge):

#[derive(Debug)]
struct Node {
    data: i32,
    next: Option<Box<Node>>,
}

fn merge_sort_list(head: Option<Box<Node>>) -> Option<Box<Node>> {
    if head.is_none() || head.as_ref().unwrap().next.is_none() {
        return head;
    }

    // Find middle using slow/fast pointers
    let mut slow = &head;
    let mut fast = &head;

    while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
        slow = &slow.as_ref().unwrap().next;
        fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;
    }

    // Split the list (this requires mutable access, simplified here)
    // In practice, you'd need to handle ownership more carefully

    // For educational purposes, showing the concept
    // A full implementation would require more complex ownership handling

    head
}

Applications

1. External sorting: Sorting data too large for memory (merge sorted chunks)
2. Linked list sorting: Natural fit due to sequential access
3. Counting inversions: Modified merge sort can count inversions in O(n log n)
4. Stable sorting requirement: When element order matters for equal keys

Counting Inversions

An inversion is a pair (i, j) where i < j but arr[i] > arr[j]:

fn count_inversions(arr: Vec<i32>) -> (Vec<i32>, usize) {
    if arr.len() <= 1 {
        return (arr, 0);
    }

    let mid = arr.len() / 2;
    let (left, left_inv) = count_inversions(arr[..mid].to_vec());
    let (right, right_inv) = count_inversions(arr[mid..].to_vec());

    let (merged, merge_inv) = merge_and_count(left, right);

    (merged, left_inv + right_inv + merge_inv)
}

fn merge_and_count(left: Vec<i32>, right: Vec<i32>) -> (Vec<i32>, usize) {
    let mut merged = Vec::new();
    let mut inversions = 0;
    let mut i = 0;
    let mut j = 0;

    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            merged.push(left[i]);
            i += 1;
        } else {
            merged.push(right[j]);
            // All remaining in left are greater than right[j]
            inversions += left.len() - i;
            j += 1;
        }
    }

    merged.extend_from_slice(&left[i..]);
    merged.extend_from_slice(&right[j..]);

    (merged, inversions)
}

fn main() {
    let arr = vec![2, 3, 8, 6, 1];
    let (_, count) = count_inversions(arr);
    println!("Inversions: {}", count); // 5
}

Comparison with Other Sorts

| Aspect | Merge Sort | Quick Sort | Heap Sort | |--------|------------|------------|-----------| | Time (worst) | O(n log n) | O(n²) | O(n log n) | | Time (avg) | O(n log n) | O(n log n) | O(n log n) | | Space | O(n) | O(log n) | O(1) | | Stable | Yes | No | No | | Cache | Poor | Good | Poor |

Key Takeaways

1. Merge sort divides, conquers, and merges
2. Always O(n log n)—guaranteed performance
3. Stable: equal elements maintain relative order
4. Requires O(n) extra space for arrays
5. Excellent for linked lists (O(log n) merge space)
6. Used in external sorting and Timsort
7. The merge operation is the key insight

Merge sort's predictable performance and stability make it a reliable choice. While quicksort is often faster in practice for arrays, merge sort excels for linked lists and when stability matters.