Merge Sort as Divide and Conquer in DSA C++ - Execution Trace

Concept Flow - Merge Sort as Divide and Conquer

Start: Full array

↓

Divide array into two halves

↓

Recursively sort left half

→Recursively sort right half

↓

Merge two sorted halves into one sorted array

↓

Return merged sorted array

↓

Done

Merge Sort splits the array into halves recursively, sorts each half, then merges them back in order.

Execution Sample

DSA C++

void mergeSort(int arr[], int left, int right) {
  if (left >= right) return;
  int mid = left + (right - left) / 2;
  mergeSort(arr, left, mid);
  mergeSort(arr, mid + 1, right);
  merge(arr, left, mid, right);
}

This code recursively divides the array and merges sorted halves.

Execution Table

Step	Operation	Subarray Indices	Action Detail	Array State
1	Divide	[0..7]	Split into [0..3] and [4..7]	[38, 27, 43, 3, 9, 82, 10, 15]
2	Divide	[0..3]	Split into [0..1] and [2..3]	[38, 27, 43, 3, 9, 82, 10, 15]
3	Divide	[0..1]	Split into [0..0] and [1..1]	[38, 27, 43, 3, 9, 82, 10, 15]
4	Base case	[0..0]	Single element, no action	[38, 27, 43, 3, 9, 82, 10, 15]
5	Base case	[1..1]	Single element, no action	[38, 27, 43, 3, 9, 82, 10, 15]
6	Merge	[0..1]	Merge [38] and [27] → [27, 38]	[27, 38, 43, 3, 9, 82, 10, 15]
7	Divide	[2..3]	Split into [2..2] and [3..3]	[27, 38, 43, 3, 9, 82, 10, 15]
8	Base case	[2..2]	Single element, no action	[27, 38, 43, 3, 9, 82, 10, 15]
9	Base case	[3..3]	Single element, no action	[27, 38, 43, 3, 9, 82, 10, 15]
10	Merge	[2..3]	Merge [43] and [3] → [3, 43]	[27, 38, 3, 43, 9, 82, 10, 15]
11	Merge	[0..3]	Merge [27, 38] and [3, 43] → [3, 27, 38, 43]	[3, 27, 38, 43, 9, 82, 10, 15]
12	Divide	[4..7]	Split into [4..5] and [6..7]	[3, 27, 38, 43, 9, 82, 10, 15]
13	Divide	[4..5]	Split into [4..4] and [5..5]	[3, 27, 38, 43, 9, 82, 10, 15]
14	Base case	[4..4]	Single element, no action	[3, 27, 38, 43, 9, 82, 10, 15]
15	Base case	[5..5]	Single element, no action	[3, 27, 38, 43, 9, 82, 10, 15]
16	Merge	[4..5]	Merge [9] and [82] → [9, 82]	[3, 27, 38, 43, 9, 82, 10, 15]
17	Divide	[6..7]	Split into [6..6] and [7..7]	[3, 27, 38, 43, 9, 82, 10, 15]
18	Base case	[6..6]	Single element, no action	[3, 27, 38, 43, 9, 82, 10, 15]
19	Base case	[7..7]	Single element, no action	[3, 27, 38, 43, 9, 82, 10, 15]
20	Merge	[6..7]	Merge [10] and [15] → [10, 15]	[3, 27, 38, 43, 9, 82, 10, 15]
21	Merge	[4..7]	Merge [9, 82] and [10, 15] → [9, 10, 15, 82]	[3, 27, 38, 43, 9, 10, 15, 82]
22	Merge	[0..7]	Merge [3, 27, 38, 43] and [9, 10, 15, 82] → [3, 9, 10, 15, 27, 38, 43, 82]	[3, 9, 10, 15, 27, 38, 43, 82]
23	Done	[0..7]	Array fully sorted	[3, 9, 10, 15, 27, 38, 43, 82]

💡 All subarrays reduced to single elements and merged back sorted

Variable Tracker

Variable	Start	After Step 6	After Step 10	After Step 11	After Step 16	After Step 20	After Step 21	After Step 22	Final
arr	[38, 27, 43, 3, 9, 82, 10, 15]	[27, 38, 43, 3, 9, 82, 10, 15]	[27, 38, 3, 43, 9, 82, 10, 15]	[3, 27, 38, 43, 9, 82, 10, 15]	[3, 27, 38, 43, 9, 82, 10, 15]	[3, 27, 38, 43, 9, 82, 10, 15]	[3, 27, 38, 43, 9, 10, 15, 82]	[3, 9, 10, 15, 27, 38, 43, 82]	[3, 9, 10, 15, 27, 38, 43, 82]
left	0	0	0	0	4	6	4	0	0
right	7	1	3	3	5	7	7	7	7
mid	3	0	2	1	4	6	5	3	3

Key Moments - 3 Insights

Why do we stop dividing when the subarray has one element?

Because a single element is already sorted. See steps 4, 5, 8, 9, 14, 15, 18, 19 where no further division happens.

How does merging keep the array sorted?

Merging compares elements from two sorted halves and picks the smaller one step-by-step, as shown in steps 6, 10, 11, 16, 20, 21, and 22.

Why do we merge after both halves are sorted?

Because merging two sorted halves produces a fully sorted larger array. This is the core of divide and conquer, shown in steps 11, 21, and 22.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after step 11?

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

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

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

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

💡 Hint

Check the 'Array State' column in row with Step 11 in execution_table.

At which step does the merge of the entire array happen?

A Step 22

B Step 21

C Step 16

D Step 6

💡 Hint

Look for the step where indices [0..7] are merged in execution_table.

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

A Array would be reversed

B Merge steps would be skipped

C Merge steps would still happen but no swaps needed

D Divide steps would be skipped

💡 Hint

Merging always happens; see variable_tracker and execution_table for merge steps.

Concept Snapshot

Merge Sort divides the array into halves recursively.
Each half is sorted separately.
Then merge combines two sorted halves into one sorted array.
Base case: single element arrays are sorted.
Time complexity: O(n log n).
Stable and efficient sorting method.

Full Transcript

Merge Sort is a sorting method that uses divide and conquer. It splits the array into smaller parts until each part has one element. Then it merges these parts back together in sorted order. The process repeats recursively. The key steps are dividing the array, sorting each half, and merging them. This method is efficient and stable, with a time complexity of O(n log n). The execution table shows each step of dividing and merging, and the variable tracker shows how the array changes after merges. Beginners often wonder why we stop dividing at one element and how merging keeps the array sorted. The answers lie in the base case and the merge process that compares elements from two sorted halves.

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