Merge Sort as Divide and Conquer in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of merge sort on this array?

Given the array [38, 27, 43, 3, 9, 82, 10], what is the sorted array after applying merge sort?

DSA C

int arr[] = {38, 27, 43, 3, 9, 82, 10};
// After merge sort, what is the array?

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

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

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

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

💡 Hint

Think about how merge sort splits and merges the array in sorted order.

Merge sort divides the array into halves recursively and merges them back in sorted order, resulting in a fully sorted array.

🧠 Conceptual

intermediate

Why does merge sort use divide and conquer?

Which of the following best explains why merge sort uses the divide and conquer approach?

A It sorts the array by swapping adjacent elements repeatedly.

B It breaks the problem into smaller parts, sorts them, then merges results to solve the big problem.

C It uses a single loop to find the smallest element and place it first.

D It sorts the array by randomly shuffling elements until sorted.

💡 Hint

Divide and conquer means breaking a big problem into smaller ones.

Merge sort divides the array into halves, sorts each half recursively, then merges the sorted halves to get the final sorted array.

❓ Predict Output

advanced

What is the output after merging two sorted halves?

Given two sorted halves: [3, 27, 38] and [9, 10, 43], what is the merged sorted array?

DSA C

int left[] = {3, 27, 38};
int right[] = {9, 10, 43};
// After merging left and right, what is the array?

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

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

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

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

💡 Hint

Merging means taking the smallest element from either half step by step.

Merging two sorted arrays results in a single sorted array by comparing elements from both halves.

🔧 Debug

advanced

What error occurs in this merge sort code snippet?

Consider this snippet from a merge sort implementation in 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++; } } What error will this code cause when compiled with standard C?

A No error, code compiles and runs correctly

B Runtime error: array index out of bounds

C Logical error: merge does not sort correctly

D Compilation error: variable length arrays not allowed in some C standards

💡 Hint

Check if variable length arrays are supported in all C standards.

Variable length arrays (L[n1], R[n2]) are not supported in C89 and some compilers without extensions, causing compilation errors.

🧠 Conceptual

expert

What is the time complexity of merge sort and why?

Which option correctly states the time complexity of merge sort and explains why?

A O(log n) because it only divides the array without merging

B O(n^2) because every element is compared with every other element

C O(n log n) because the array is divided into halves log n times and merging takes linear time each level

D O(n) because it sorts the array in a single pass

💡 Hint

Think about how many times the array is split and how merging works.

Merge sort divides the array into halves log n times and merges each level in linear time, resulting in O(n log n) complexity.

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