Merge Sort as Divide and Conquer in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to split the array into two halves in Merge Sort.

DSA C#

int mid = arr.Length [1] 2;

Drag options to blanks, or click blank then click option'

A/

B+

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition or multiplication instead of division to find the middle.

Using subtraction which does not give the middle index.

We divide the length by 2 to find the middle index for splitting the array.

2fill in blank

medium

Complete the code to copy the left half of the array in Merge Sort.

DSA C#

Array.Copy(arr, 0, left, 0, [1]);

Drag options to blanks, or click blank then click option'

Aleft.Length

Barr.Length

Cmid

Darr.Length / 2 + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using the full array length instead of mid.

Using left.Length which might not be set correctly.

We copy from index 0 to mid length to get the left half.

3fill in blank

hard

Fix the error in the merge function to correctly compare elements.

DSA C#

if (left[i] [1] right[j])

Drag options to blanks, or click blank then click option'

A<

B>

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using greater than which reverses sorting order.

Using equality which does not help in sorting.

We compare if left element is less than right to merge in sorted order.

4fill in blank

hard

Fill both blanks to complete the recursive calls for Merge Sort.

DSA C#

MergeSort([1]);
MergeSort([2]);

Drag options to blanks, or click blank then click option'

Aleft

Bright

Carr

Dtemp

Attempts:

3 left

💡 Hint

Common Mistakes

Calling MergeSort on the original array twice.

Using a temporary array instead of left or right.

We recursively sort the left and right halves separately.

5fill in blank

hard

Fill all three blanks to complete the merge logic copying remaining elements.

DSA C#

while (i < [1]) arr[k++] = left[i++];
while (j < [2]) arr[k++] = right[j++];
return [3];

Drag options to blanks, or click blank then click option'

Aleft.Length

Bright.Length

Carr

Dtemp

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong array lengths in loops causing index errors.

Returning a temporary array instead of the merged array.

We copy remaining elements from left and right arrays and return the merged array.

Practice

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

easy

A. Insert elements one by one into a sorted list

B. Divide the list into smaller parts, sort them, then merge back

C. Pick a pivot and partition the list around it

D. Sort the list by swapping adjacent elements repeatedly

Solution

1. Step 1: Understand divide and conquer

   Merge Sort splits the list into smaller parts to handle sorting easily.

2. Step 2: Merge sorted parts

   After sorting smaller parts, it merges them to get the final sorted list.

3. Final Answer:

   Divide the list into smaller parts, sort them, then merge back -> Option B

4. Quick Check:

   Merge Sort = Divide and conquer sorting [OK]

Hint: Remember: split, sort, then merge [OK]

Common Mistakes:

• Confusing Merge Sort with Bubble Sort
• Thinking Merge Sort sorts in place without merging
• Mixing up Merge Sort with Quick Sort

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 right)

C. void merge(int arr[], int start, int end)

D. int MergeSort(int[] arr, int left, int right)

Solution

1. Step 1: Identify merge function purpose

   Merge combines two sorted parts, so it needs array and indices for left, mid, right.

2. Step 2: Check correct signature

   void Merge(int[] arr, int left, int mid, int right) matches void return type and parameters for merging parts.

3. Final Answer:

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

4. Quick Check:

   Merge function signature = void Merge(int[] arr, int left, int mid, int right) [OK]

Hint: Merge needs array and three indices: left, mid, right [OK]

Common Mistakes:

• Using return type int instead of void for merge
• Confusing merge with mergeSort function signature
• Wrong parameter names or missing mid index

3. What will be the output of the following C# code snippet using Merge Sort on array {4, 1, 3, 2}?

int[] arr = {4, 1, 3, 2};
MergeSort(arr, 0, arr.Length - 1);
Console.WriteLine(string.Join(", ", arr));

medium

A. 1, 3, 2, 4

B. 4, 3, 2, 1

C. 1, 2, 3, 4

D. 2, 1, 3, 4

Solution

1. Step 1: Apply Merge Sort on array {4, 1, 3, 2}

   Split into {4,1} and {3,2}, sort each to {1,4} and {2,3}.

2. Step 2: Merge sorted halves

   Merge {1,4} and {2,3} to get fully sorted {1,2,3,4}.

3. Final Answer:

   1, 2, 3, 4 -> Option C

4. Quick Check:

   Sorted array = 1, 2, 3, 4 [OK]

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

Common Mistakes:

• Confusing merge step order
• Assuming original order remains
• Mixing up indices during merge

4. Identify the error in this Merge Sort code snippet:

void MergeSort(int[] arr, int left, int right) {
  if (left < right) {
    int mid = (left + right) / 2;
    MergeSort(arr, left, mid);
    MergeSort(arr, mid, right);
    Merge(arr, left, mid, right);
  }
}

medium

A. The second recursive call should be MergeSort(arr, mid + 1, right)

B. The mid calculation should be mid = (left + right + 1) / 2

C. Merge function should be called before recursive calls

D. The base condition should be if (left <= right)

Solution

1. Step 1: Check recursive calls ranges

   Second call uses mid as start, but it should start from mid + 1 to avoid overlap.

2. Step 2: Correct recursive call

   Change second call to MergeSort(arr, mid + 1, right) to cover right half properly.

3. Final Answer:

   The second recursive call should be MergeSort(arr, mid + 1, right) -> Option A

4. Quick Check:

   Correct recursive ranges avoid overlap [OK]

Hint: Right half starts at mid + 1, not mid [OK]

Common Mistakes:

• Using mid instead of mid + 1 for right half
• Calling merge before sorting halves
• Wrong base condition causing infinite recursion

5. Given a large array with many duplicate values, how can you modify Merge Sort to improve performance by avoiding unnecessary merges?

hard

A. Skip sorting the left half if it contains duplicates

B. Merge halves only if their sizes are equal

C. Use a hash set to remove duplicates before sorting

D. Check if the last element of left half is less or equal to first element of right half before merging

Solution

1. Step 1: Understand optimization for duplicates

   If left half's max ≤ right half's min, they are already sorted relative to each other.

2. Step 2: Skip merge if condition met

   By checking this, we avoid merging which saves time on duplicates.

3. Final Answer:

   Check if the last element of left half is less or equal to first element of right half before merging -> Option D

4. Quick Check:

   Skip merge if halves already ordered [OK]

Hint: Skip merge if halves already sorted relative to each other [OK]

Common Mistakes:

• Removing duplicates before sorting changes data
• Skipping sorting halves based on duplicates
• Merging only equal sized halves is incorrect