Merge Sort Algorithm in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Merge Sort on a small array

What is the output of the following merge sort implementation when sorting the array [4, 1, 3, 2]?

DSA C

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int 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];
            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(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[] = {4, 1, 3, 2};
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, 0, arr_size - 1);
    for (int i = 0; i < arr_size; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

A 1 3 2 4

B 4 3 2 1

C 1 2 3 4

D 2 1 3 4

💡 Hint

Trace how the array is split and merged step by step.

The merge sort splits the array into halves recursively until single elements remain, then merges them back in sorted order. The final sorted array is 1 2 3 4.

🧠 Conceptual

intermediate

Time complexity of Merge Sort

What is the time complexity of merge sort in the average and worst cases?

A O(n log n)

B O(n)

C O(log n)

D O(n^2)

💡 Hint

Think about how many times the array is split and merged.

Merge sort divides the array into halves recursively (log n splits) and merges them (n operations per merge), resulting in O(n log n) time complexity.

🔧 Debug

advanced

Identify the bug in this merge function

What error will occur when running this merge function on an array segment?

DSA C

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int 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];
            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++;
    }
}

A No error, code runs correctly

B Array index out of bounds error due to incorrect loop condition in copying L array

C Infinite loop in merging while loop

D Segmentation fault due to uninitialized pointers

💡 Hint

Check the loop that copies elements into L array carefully.

The loop copying elements into L uses i <= n1 which goes one past the array size, causing out of bounds access.

🚀 Application

advanced

Using Merge Sort to count inversions

How can merge sort be modified to count the number of inversions (pairs where a[i] > a[j] and i < j) in an array?

A Count inversions only in the left half recursively

B Count inversions by comparing every pair after sorting

C Count inversions by sorting the array twice

D Count inversions during the merge step when elements from the right array are placed before left array elements

💡 Hint

Think about when elements from the right half are smaller than those in the left half during merging.

During the merge step, when an element from the right half is placed before one from the left, it indicates inversions equal to the remaining elements in the left half.

🧠 Conceptual

expert

Space complexity of Merge Sort

What is the space complexity of the standard merge sort algorithm and why?

A O(n) because it requires temporary arrays to merge sorted halves

B O(log n) because it uses recursion stack only

C O(1) because it sorts in place without extra memory

D O(n log n) because it copies the array multiple times

💡 Hint

Consider the temporary arrays used during merging.

Standard merge sort uses temporary arrays to hold halves during merging, requiring O(n) extra space. The recursion stack uses O(log n), but the dominant space is from these arrays.

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