Lab 2: Merge Sort (Divide and Conquer)

In this lab, we will study Merge Sort, a classic divide and conquer algorithm.
We will implement it recursively and explore the theoretical iterative (bottom-up) version.
We will also analyze time complexity, space complexity, and observe its stability and sorting order guarantees.

We demonstrate both:

• Recursive Merge Sort (top-down division and merging)
• Iterative Merge Sort (bottom-up merging without explicit recursion)

Problem Definition

Given an unsorted array $A$ of length $n$, produce a sorted array in non-decreasing order using the merge sort strategy.

Algorithmic Strategy

Divide and Conquer Steps:

1. Divide: Split the array into two halves.
2. Conquer: Sort each half recursively.
3. Combine: Merge the two sorted halves into a single sorted array.

Mathematical Recurrence

Let $T(n)$ be the time complexity of merge sort:

• Explanation:
  • $2T\left(\frac{n}{2}\right)$ for sorting the two halves
  • $\Theta(n)$ for merging two sorted lists of total size $n$

Using the Master Theorem ($a = 2$, $b = 2$, $f(n) = \Theta(n)$):
$T(n) = \Theta(n \log n)$.

Implementation

# Recursive Merge Sort
def merge_sort_recursive(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort_recursive(arr[:mid])
    right = merge_sort_recursive(arr[mid:])
    return merge(left, right)
 
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
 
# Iterative (Bottom-Up) Merge Sort
def merge_sort_iterative(arr):
    width = 1
    n = len(arr)
    while width < n:
        for i in range(0, n, 2 * width):
            left = arr[i:i + width]
            right = arr[i + width:i + 2 * width]
            arr[i:i + 2 * width] = merge(left, right)
        width *= 2
    return arr
 
# Driver
arr = [38, 27, 43, 3, 9, 82, 10]
print("Recursive:", merge_sort_recursive(arr))
print("Iterative:", merge_sort_iterative(arr.copy()))

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> merge(vector<int> left, vector<int> right) {
    vector<int> result;
    int i = 0, j = 0;
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) result.push_back(left[i++]);
        else result.push_back(right[j++]);
    }
    while (i < left.size()) result.push_back(left[i++]);
    while (j < right.size()) result.push_back(right[j++]);
    return result;
}
 
vector<int> merge_sort_recursive(vector<int> arr) {
    if (arr.size() <= 1) return arr;
    int mid = arr.size() / 2;
    vector<int> left(arr.begin(), arr.begin() + mid);
    vector<int> right(arr.begin() + mid, arr.end());
    left = merge_sort_recursive(left);
    right = merge_sort_recursive(right);
    return merge(left, right);
}
 
int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    vector<int> sorted = merge_sort_recursive(arr);
    cout << "Recursive: ";
    for (int x : sorted) cout << x << " ";
    cout << endl;
    return 0;
}

// Merge function
function merge(left, right) {
  let result = [],
    i = 0,
    j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}
 
// Recursive Merge Sort
function merge_sort_recursive(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = merge_sort_recursive(arr.slice(0, mid));
  const right = merge_sort_recursive(arr.slice(mid));
  return merge(left, right);
}
 
const arr = [38, 27, 43, 3, 9, 82, 10];
console.log("Recursive:", merge_sort_recursive(arr));

Expected Output

For input:

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

Output:

Recursive: [3, 9, 10, 27, 38, 43, 82]
Iterative: [3, 9, 10, 27, 38, 43, 82]

Time and Space Complexity Analysis

• Best, Average, Worst Case Time: All $O(n \log n)$, because splitting and merging steps are the same regardless of input order.
• Space: Needs auxiliary storage proportional to $n$. In-place mergesort exists but is complex and not stable.
• Stability: Merge sort preserves the order of equal elements.

Practice

LeetCode

• Merge Sorted Array - #88 
  Merge two sorted arrays into one sorted array in place. Focuses on merging logic without recursion.

• Merge Two Sorted Lists - #21 
  Merge two sorted linked lists into one sorted linked list. Highlights pointer manipulation and stability.

• Merge Intervals - #56 
  Given overlapping intervals, merge them into non-overlapping intervals. Demonstrates sorting + merging steps.

• Sort an Array - #912 
  Sort an array without built-in functions. Merge Sort is a recommended solution, along with other algorithms.

CodeChef

• Introduction to Merge Sort - DAA012 
  Implement merge and sort functions using the merge sort technique.

• Merge Sorted Arrays (Visa Interview Practice) - SESO43 
  Implement mergeSort to sort an array, reinforcing the divide-and-conquer approach.

References

1. Python Official Documentation 

2. C++ Reference 

3. JavaScript MDN 

4. C++ Standard Template Library 

5. CS50x Week 3: Algorithms. (2025). Harvard University. Retrieved from https://cs50.harvard.edu/x/2025/weeks/3/ 

6. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C.
   Introduction to Algorithms, 3rd/4th Edition, MIT Press.