Merge Sort as Divide and Conquer in DSA C++

Mental Model

Split the list into smaller parts, sort each part, then join them back in order.

Analogy: Imagine sorting a messy pile of cards by splitting it into small piles, sorting each small pile, then carefully combining them into one sorted pile.

Unsorted array:
[7, 3, 5, 1]

Split into halves:
[7, 3]   [5, 1]

Split again:
[7] [3]   [5] [1]

Merge sorted:
[3, 7]   [1, 5]

Final merge:
[1, 3, 5, 7]

Dry Run Walkthrough

Input: array: [7, 3, 5, 1]

Goal: Sort the array in ascending order using merge sort

Step 1: Split array [7, 3, 5, 1] into two halves [7, 3] and [5, 1]

[7, 3]   [5, 1]

Why: Divide the problem into smaller parts to sort separately

Step 2: Split left half [7, 3] into [7] and [3]

[7]   [3]   [5, 1]

Why: Keep dividing until each part has one element

Step 3: Split right half [5, 1] into [5] and [1]

[7]   [3]   [5]   [1]

Why: Each part now has one element, ready to merge

Step 4: Merge [7] and [3] into sorted [3, 7]

[3, 7]   [5]   [1]

Why: Combine two sorted parts into one sorted part

Step 5: Merge [5] and [1] into sorted [1, 5]

[3, 7]   [1, 5]

Why: Combine two sorted parts into one sorted part

Step 6: Merge [3, 7] and [1, 5] into fully sorted [1, 3, 5, 7]

[1, 3, 5, 7]

Why: Final merge to get the fully sorted array

Result:

[1, 3, 5, 7]

Annotated Code

DSA C++

#include <iostream>
#include <vector>

void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    std::vector<int> L(n1);
    std::vector<int> R(n2);

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid); // sort left half
        mergeSort(arr, mid + 1, right); // sort right half
        merge(arr, left, mid, right); // merge sorted halves
    }
}

int main() {
    std::vector<int> arr = {7, 3, 5, 1};
    mergeSort(arr, 0, arr.size() - 1);
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

if (left < right) {

check if the current part has more than one element to split

int mid = left + (right - left) / 2;

find middle index to split array

mergeSort(arr, left, mid); // sort left half

recursively sort left half

mergeSort(arr, mid + 1, right); // sort right half

recursively sort right half

merge(arr, left, mid, right); // merge sorted halves

combine two sorted halves into one sorted part

while (i < n1 && j < n2) {

merge elements from left and right arrays in order

arr[k] = L[i]; i++;

take element from left if smaller or equal

arr[k] = R[j]; j++;

take element from right if smaller

while (i < n1) { arr[k] = L[i]; i++; k++; }

copy remaining elements from left if any

while (j < n2) { arr[k] = R[j]; j++; k++; }

copy remaining elements from right if any

Output

1 3 5 7 

Complexity Analysis

Time: O(n log n) because the array is repeatedly split in half (log n splits) and merging takes linear time at each level

Space: O(n) because temporary arrays are used to merge parts

vs Alternative: Compared to simple sorting like bubble sort O(n^2), merge sort is much faster for large arrays due to divide and conquer

Edge Cases

empty array

function returns immediately without changes

DSA C++

if (left < right) {

array with one element

function returns immediately because single element is already sorted

DSA C++

if (left < right) {

array with duplicate elements

duplicates are handled correctly and appear in sorted order

DSA C++

if (L[i] <= R[j]) {

When to Use This Pattern

When you need to sort data efficiently and can split the problem into smaller parts, use merge sort because it divides and conquers to sort in O(n log n) time.

Common Mistakes

Mistake: Not checking the base case properly, causing infinite recursion
Fix: Add condition if (left < right) to stop splitting when one element remains

Mistake: Merging without copying remaining elements from left or right arrays
Fix: Add loops to copy leftover elements after main merge loop

Summary

It sorts an array 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 data.

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. Select a pivot and partition the array around it

B. Sort the array by repeatedly swapping adjacent elements

C. Divide the array into halves, sort each half, then merge them

D. Insert elements one by one into a sorted list

Solution

1. Step 1: Understand the divide and conquer approach

   Merge Sort splits the array into two halves recursively until single elements remain.

2. Step 2: Merge sorted halves

   After splitting, it merges the halves back in sorted order to form the sorted array.

3. Final Answer:

   Divide the array into halves, sort each half, then merge them -> Option C

4. Quick Check:

   Merge Sort = Divide, sort halves, merge [OK]

Hint: Remember: split, sort halves, then merge [OK]

Common Mistakes:

• Confusing Merge Sort with Bubble Sort
• Thinking Merge Sort uses a pivot like Quick Sort
• Believing Merge Sort sorts in place without merging

2. Which of the following is the correct base case condition in a typical Merge Sort implementation in C++?

easy

A. if (start > end) return;

B. if (start < end) return;

C. if (start == end + 1) return;

D. if (start >= end) return;

Solution

1. Step 1: Identify when to stop recursion

   The base case is when the subarray has one or zero elements, meaning start index is greater or equal to end index.

2. Step 2: Match condition to code

   The condition if (start >= end) return; correctly stops recursion when the subarray cannot be divided further.

3. Final Answer:

   if (start >= end) return; -> Option D

4. Quick Check:

   Base case = start >= end [OK]

Hint: Stop recursion when start is not less than end [OK]

Common Mistakes:

• Using start > end misses single element subarray
• Using start == end + 1 is incorrect indexing
• Using start < end returns too early

3. What will be the output of the following C++ code snippet using Merge Sort on array {4, 1, 3, 2}?

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
}

int main() {
    int arr[] = {4, 1, 3, 2};
    int n = 4;
    mergeSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) std::cout << arr[i] << " ";
    return 0;
}

medium

A. 1 2 3 4

B. 4 3 2 1

C. 1 3 2 4

D. 2 1 3 4

Solution

1. Step 1: Trace recursive splitting and merging

   The array splits into [4,1] and [3,2], then further into single elements. Each pair is merged sorted: [1,4] and [2,3].

2. Step 2: Final merge

   Merging [1,4] and [2,3] results in [1,2,3,4]. The output prints this sorted array.

3. Final Answer:

   1 2 3 4 -> Option A

4. Quick Check:

   Sorted array = 1 2 3 4 [OK]

Hint: Merge Sort always outputs sorted array [OK]

Common Mistakes:

• Confusing merge order causing wrong output
• Forgetting to merge after recursive calls
• Printing array before sorting completes

4. Identify the bug in this Merge Sort merge function snippet:

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i <= n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

medium

A. The loop 'for (int i = 0; i <= n1; i++)' causes out-of-bounds access

B. The merge condition should be 'L[i] < R[j]' instead of '<='

C. The arrays L and R should be dynamically allocated

D. The indices i and j should start from 1, not 0

Solution

1. Step 1: Check loop bounds for copying left array

   The loop uses 'i <= n1', which runs one extra iteration causing out-of-bounds access since valid indices are 0 to n1-1.

2. Step 2: Correct loop condition

   The loop should be 'i < n1' to copy exactly n1 elements without overflow.

3. Final Answer:

   The loop 'for (int i = 0; i <= n1; i++)' causes out-of-bounds access -> Option A

4. Quick Check:

   Loop bounds must be less than array size [OK]

Hint: Check array loops use < not <= for indexing [OK]

Common Mistakes:

• Using <= instead of < in loops
• Starting indices at 1 instead of 0
• Ignoring dynamic allocation but it's not mandatory here

5. Given an array {5, 3, 8, 6, 2, 7, 4, 1}, how many total merge operations will be performed during a full Merge Sort?

hard

A. 15

B. 7

C. 8

D. 4

Solution

1. Step 1: Understand merge operations in Merge Sort

   Merge Sort splits the array until single elements, then merges pairs stepwise. For n=8 elements, merges happen at each level combining subarrays.

2. Step 2: Calculate total merges

   Number of merges = n - 1 = 8 - 1 = 7 merges in total to combine all elements into one sorted array.

3. Final Answer:

   7 -> Option B

4. Quick Check:

   Total merges = n - 1 = 7 [OK]

Hint: Total merges in Merge Sort = array size minus one [OK]

Common Mistakes:

• Counting merges as number of elements
• Confusing merges with recursive calls
• Assuming merges double at each level