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.