Merge Sort Algorithm in DSA C - Execution Trace

Concept Flow - Merge Sort Algorithm

Start with full array

↓

Divide array into two halves

↓

Recursively apply merge sort on left half

↓

Base case: single element or empty

↓

Merge two sorted halves

↓

Sorted full array

↓

Done

Merge Sort splits the array into halves recursively until single elements remain, then merges sorted halves back together.

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 splits the array and merges sorted parts to sort the entire array.

Execution Table

Step	Operation	Sub-array Range	Action Detail	Array State
1	Split	[0..7]	mid=3, split into [0..3] and [4..7]	[38, 27, 43, 3, 9, 82, 10, 15]
2	Split	[0..3]	mid=1, split into [0..1] and [2..3]	[38, 27, 43, 3, 9, 82, 10, 15]
3	Split	[0..1]	mid=0, split into [0..0] and [1..1]	[38, 27, 43, 3, 9, 82, 10, 15]
4	Base case	[0..0]	single element 38	[38, 27, 43, 3, 9, 82, 10, 15]
5	Base case	[1..1]	single element 27	[38, 27, 43, 3, 9, 82, 10, 15]
6	Merge	[0..1]	merge [38] and [27]	[27, 38, 43, 3, 9, 82, 10, 15]
7	Split	[2..3]	mid=2, split into [2..2] and [3..3]	[27, 38, 43, 3, 9, 82, 10, 15]
8	Base case	[2..2]	single element 43	[27, 38, 43, 3, 9, 82, 10, 15]
9	Base case	[3..3]	single element 3	[27, 38, 43, 3, 9, 82, 10, 15]
10	Merge	[2..3]	merge [43] and [3]	[27, 38, 3, 43, 9, 82, 10, 15]
11	Merge	[0..3]	merge [27, 38] and [3, 43]	[3, 27, 38, 43, 9, 82, 10, 15]
12	Split	[4..7]	mid=5, split into [4..5] and [6..7]	[3, 27, 38, 43, 9, 82, 10, 15]
13	Split	[4..5]	mid=4, split into [4..4] and [5..5]	[3, 27, 38, 43, 9, 82, 10, 15]
14	Base case	[4..4]	single element 9	[3, 27, 38, 43, 9, 82, 10, 15]
15	Base case	[5..5]	single element 82	[3, 27, 38, 43, 9, 82, 10, 15]
16	Merge	[4..5]	merge [9] and [82]	[3, 27, 38, 43, 9, 82, 10, 15]
17	Split	[6..7]	mid=6, split into [6..6] and [7..7]	[3, 27, 38, 43, 9, 82, 10, 15]
18	Base case	[6..6]	single element 10	[3, 27, 38, 43, 9, 82, 10, 15]
19	Base case	[7..7]	single element 15	[3, 27, 38, 43, 9, 82, 10, 15]
20	Merge	[6..7]	merge [10] and [15]	[3, 27, 38, 43, 9, 82, 10, 15]
21	Merge	[4..7]	merge [9, 82] and [10, 15]	[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]
23	Done	Full array sorted	Final sorted array	[3, 9, 10, 15, 27, 38, 43, 82]

💡 All sub-arrays reduced to single elements and merged back fully 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, 27, 38, 43, 9, 10, 15, 82]	[3, 9, 10, 15, 27, 38, 43, 82]
left	0	0	0	0	4	4	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 split the array until single elements before merging?

Because single elements are already sorted, merging them step-by-step creates sorted bigger arrays. See steps 4,5,8,9 where base cases are reached before merges in steps 6,10.

Why does the merge step reorder elements in the array?

Merge compares elements from two sorted halves and places the smaller first, ensuring the merged array is sorted. Look at step 6 merging [38] and [27] into [27, 38].

How does the algorithm know when to stop splitting?

When the sub-array has one or zero elements (left >= right), it stops splitting. This is shown in base cases at steps 4,5,8,9,14,15,18,19.

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 ]51 ,01 ,28 ,9 ,34 ,83 ,72 ,3[

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

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

💡 Hint

Check the 'Array State' column for step 11 in the execution_table.

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

A Step 22

B Step 20

C Step 21

D Step 23

💡 Hint

Look for the step merging [0..7] in the 'Sub-array Range' column.

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

A No merges would happen

B Merge steps would still happen but no swaps needed

C Splitting would not happen

D Array would be reversed

💡 Hint

Merging always happens; sorted arrays just merge without reordering.

Concept Snapshot

Merge Sort Algorithm:
- Recursively split array into halves until single elements
- Merge sorted halves by comparing elements
- Time complexity: O(n log n)
- Stable and works well for large data
- Uses extra space for merging
- Divide and conquer approach

Full Transcript

Merge Sort Algorithm splits the array into two halves recursively until each sub-array has one element. Then it merges these small sorted arrays step-by-step to form larger sorted arrays until the full array is sorted. The process involves dividing, base case detection, and merging. The array state changes after each merge, showing sorted sub-arrays growing in size. This method ensures efficient sorting with O(n log n) time complexity.

Practice

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

easy

A. Insert elements one by one into a sorted sublist

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

C. Select a pivot and partition the array around it

D. Sort the array by repeatedly swapping adjacent elements

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

   It then merges these sorted halves to produce a fully sorted array.

3. Final Answer:

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

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 extra space

2. Which of the following is the correct way to declare the merge function header in C for Merge Sort?

easy

A. void merge(int arr[], int left, int mid, int right);

B. int merge(int arr, int left, int mid, int right);

C. void merge(int arr, int left, int mid, int right);

D. int merge(int arr[], int left, int right);

Solution

1. Step 1: Check parameter types for merge function

   The array should be passed as int arr[] and indices as integers.

2. Step 2: Confirm return type

   Merge function usually returns nothing (void) as it modifies the array in place.

3. Final Answer:

   void merge(int arr[], int left, int mid, int right); -> Option A

4. Quick Check:

   Correct signature = void merge(int arr[], int left, int mid, int right); [OK]

Hint: Array as int arr[], return void for merge [OK]

Common Mistakes:

• Passing array as int arr instead of int arr[]
• Using int return type instead of void
• Missing the mid parameter needed for merging

3. What will be the output of the following code snippet after calling mergeSort(arr, 0, 4); on int arr[] = {5, 3, 8, 4, 2};?

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], 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++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

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

medium

A. [3, 5, 4, 2, 8]

B. [5, 3, 8, 4, 2]

C. [2, 3, 4, 5, 8]

D. [8, 5, 4, 3, 2]

Solution

1. Step 1: Understand recursive splitting

   The array is split into halves recursively until single elements remain: [5,3,8,4,2] -> [5,3,8] and [4,2], then further splits.

2. Step 2: Merge sorted halves step-by-step

   After sorting and merging, the final array becomes sorted in ascending order: [2, 3, 4, 5, 8].

3. Final Answer:

   [2, 3, 4, 5, 8] -> Option C

4. Quick Check:

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

Hint: Merge Sort always returns sorted array ascending [OK]

Common Mistakes:

• Assuming original array remains unchanged
• Confusing mergeSort with other sorting algorithms
• Forgetting to merge after recursive calls

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

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], 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++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

medium

A. The array sizes n1 and n2 are calculated incorrectly

B. The merge function should return an int instead of void

C. The while loops conditions should be i <= n1 and j <= n2

D. The for loops use <= instead of < causing out-of-bounds access

Solution

1. Step 1: Check for loop boundary errors

   The for loops use <= which causes the loop to run one extra time, leading to out-of-bounds array access.

2. Step 2: Correct loop conditions

   Changing <= to < fixes the loops to iterate exactly n1 and n2 times without overflow.

3. Final Answer:

   The for loops use <= instead of < causing out-of-bounds access -> Option D

4. Quick Check:

   Loop boundary off by one = The for loops use <= instead of < causing out-of-bounds access [OK]

Hint: Use <, not <=, for array index loops [OK]

Common Mistakes:

• Using <= in loops causing overflow
• Confusing return type of merge function
• Changing while loop conditions incorrectly

5. Given an array int arr[] = {12, 11, 13, 5, 6, 7};, how many total merge operations will be performed during a full Merge Sort on this array?

hard

A. 5

B. 7

C. 6

D. 8

Solution

1. Step 1: Understand merge operations count

   For an array of size n, Merge Sort performs n-1 merge operations combining subarrays stepwise.

2. Step 2: Calculate for n=6

   Here, n=6, so total merges = 6 - 1 = 5 merges.

3. Step 3: Count merges carefully

   Levels: - Level 1: 3 merges (pairs of size 1) - Level 2: 2 merges (subarrays of size 2 and 3) Total merges = 3 + 2 = 5 merges.

4. Final Answer:

   5 -> Option A

5. Quick Check:

   Count merges per level = 5 [OK]

Hint: Count merges per level, sum all levels [OK]

Common Mistakes:

• Assuming merges = n-1 without counting levels
• Counting only one level of merges
• Confusing merge operations with comparisons