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

Concept Flow - Merge Sort as Divide and Conquer

Start with full array

↓

Divide array into two halves

↓

Recursively sort left half

→Recursively sort right half

↓

Merge two sorted halves

↓

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) {
    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	Sub-array 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] into sorted [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] into sorted [3, 43]	[27, 38, 3, 43, 9, 82, 10, 15]
11	Merge	[0..3]	Merge [27, 38] and [3, 43] into sorted [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] into sorted [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] into sorted [10, 15]	[3, 27, 38, 43, 9, 82, 10, 15]
21	Merge	[4..7]	Merge [9, 82] and [10, 15] into sorted [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] into sorted [3, 9, 10, 15, 27, 38, 43, 82]	[3, 9, 10, 15, 27, 38, 43, 82]
23	Done	Full array	Array fully sorted	[3, 9, 10, 15, 27, 38, 43, 82]

💡 All sub-arrays 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	4	4	0	0
right	7	7	7	7	7	7	7	7	7
mid	3	1	2	3	5	6	7	3	7

Key Moments - 3 Insights

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

Because a single element is already sorted, so no further division or merging is needed. See steps 4, 5, 8, 9, 14, 15, 18, 19 in the execution_table.

How does merging two sorted halves keep the array sorted?

Merging compares elements from both halves and picks the smaller one each time, building a sorted combined array. See steps 6, 10, 11, 16, 20, 21, 22 for merging details.

Why do we calculate mid as (left + right) / 2?

To split the array roughly in half for balanced division, ensuring efficient sorting. This is shown in variable_tracker where mid changes as sub-arrays change.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the array state after merging?

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

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

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

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

💡 Hint

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

At which step does the full array become completely sorted?

A Step 21

B Step 22

C Step 23

D Step 20

💡 Hint

Look for 'Done' operation and final sorted array in execution_table.

If the initial array had only 4 elements, how would the number of divide steps change?

A It would increase

B It would decrease

C It would stay the same

D It would be zero

💡 Hint

Fewer elements mean fewer splits; check divide steps in execution_table.

Concept Snapshot

Merge Sort divides array into halves recursively
Sorts each half separately
Merges sorted halves into one sorted array
Uses mid = (left + right) / 2 to split
Stops dividing when sub-array size is 1
Merging compares and combines sorted halves

Full Transcript

Merge Sort works by splitting the array into smaller parts until each part has one element. Then it merges these parts back together in sorted order. The code divides the array by calculating the middle index and recursively sorting the left and right halves. When merging, it compares elements from both halves and builds a sorted array. This process continues until the entire array is sorted. The execution table shows each divide and merge step with the array state. Key points include stopping division at single elements and merging sorted halves carefully to maintain order.

Practice

1. What is the main idea behind the Merge Sort algorithm?

easy

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

B. Sort the array by repeatedly swapping adjacent elements

C. Select a pivot and partition the array around it

D. Insert elements one by one into a sorted sublist

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 sorted halves back to form a sorted array.

3. Final Answer:

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

4. Quick Check:

   Merge Sort = Divide and Conquer [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 recursive Merge Sort function in C?

easy

A. if (start >= end) return;

B. if (start > end) return;

C. if (start == end) return;

D. if (start != end) return;

Solution

1. Step 1: Identify when recursion should stop

   Merge Sort stops splitting when the subarray has one or zero elements, i.e., start >= end.

2. Step 2: Choose the correct condition

   The base case is when start >= end, so return without further splitting.

3. Final Answer:

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

4. Quick Check:

   Base case = start >= end [OK]

Hint: Stop recursion when start >= end [OK]

Common Mistakes:

• Using == instead of >= risks issues if start > end
• Using > misses the single element case
• Using != returns too early, breaking recursion

3. What will be the output of the following C code snippet after calling mergeSort(arr, 0, 4); on int arr[] = {5, 3, 8, 4, 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) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    mergeSort(arr, 0, 4);
    for (int i = 0; i < 5; i++) printf("%d ", arr[i]);
    return 0;
}

medium

A. 5 3 8 4 2

B. 8 5 4 3 2

C. 2 3 4 5 8

D. 2 4 3 5 8

Solution

1. Step 1: Understand mergeSort splits and merges

   The array is recursively split into halves and merged in sorted order.

2. Step 2: Trace the final sorted array

   After full recursion and merging, the array becomes sorted: 2 3 4 5 8.

3. Final Answer:

   2 3 4 5 8 -> Option C

4. Quick Check:

   Sorted array output = 2 3 4 5 8 [OK]

Hint: Merge Sort always outputs sorted array [OK]

Common Mistakes:

• Thinking mergeSort does not change original array
• Confusing mergeSort with reverse sorting
• Ignoring the merge step results in unsorted output

4. Identify the error in the following merge function snippet used in Merge Sort:

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 merge function should not use temporary arrays

B. The loops copying to L and R arrays use <= instead of < causing out-of-bounds access

C. The size of arrays L and R is calculated incorrectly

D. The merge condition should be L[i] < R[j] instead of <= to avoid duplicates

Solution

1. Step 1: Check array copying loops

   The loops use i <= n1 and j <= n2 which causes index to go out of bounds since arrays are 0-based.

2. Step 2: Correct loop condition

   Loops should use i < n1 and j < n2 to avoid accessing invalid memory.

3. Final Answer:

   The loops copying to L and R arrays use <= instead of < causing out-of-bounds access -> Option B

4. Quick Check:

   Loop bounds must be less than array size [OK]

Hint: Use < not <= in loops for array indexing [OK]

Common Mistakes:

• Using <= causes buffer overflow errors
• Confusing array size with last index
• Ignoring array indexing starting at 0

5. You want to sort a linked list using Merge Sort. Which of the following is the best approach to split the list into two halves efficiently?

hard

A. Convert the list to an array, sort it, then rebuild the list

B. Count the total nodes first, then traverse again to the middle node

C. Split the list by breaking after the first node repeatedly

D. Use two pointers: move one pointer twice as fast as the other to find the middle

Solution

1. Step 1: Understand splitting linked list for Merge Sort

   Using two pointers (slow and fast), where fast moves twice as fast, helps find the middle in one pass.

2. Step 2: Compare other methods

   Counting nodes requires two passes; breaking after first node is incorrect; converting to array is inefficient.

3. Final Answer:

   Use two pointers: move one pointer twice as fast as the other to find the middle -> Option D

4. Quick Check:

   Two-pointer technique = efficient split [OK]

Hint: Use slow-fast pointer to find middle in one pass [OK]

Common Mistakes:

• Counting nodes wastes time with two traversals
• Breaking after first node does not split evenly
• Converting to array loses linked list benefits