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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Merge Sort on a small array

What is the printed output of the following C# code after performing merge sort on the array?

DSA C#

using System;

class Program {
    static void Merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        int[] L = new int[n1];
        int[] R = new int[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 iIndex = 0, jIndex = 0, k = l;
        while (iIndex < n1 && jIndex < n2) {
            if (L[iIndex] <= R[jIndex]) {
                arr[k] = L[iIndex];
                iIndex++;
            } else {
                arr[k] = R[jIndex];
                jIndex++;
            }
            k++;
        }
        while (iIndex < n1) {
            arr[k] = L[iIndex];
            iIndex++;
            k++;
        }
        while (jIndex < n2) {
            arr[k] = R[jIndex];
            jIndex++;
            k++;
        }
    }

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

    static void Main() {
        int[] arr = {5, 2, 9, 1};
        MergeSort(arr, 0, arr.Length - 1);
        for (int i = 0; i < arr.Length; i++) {
            Console.Write(arr[i]);
            if (i != arr.Length - 1) Console.Write(" -> ");
        }
        Console.WriteLine(" -> null");
    }
}

A 2 -> 1 -> 5 -> 9 -> null

B 5 -> 2 -> 9 -> 1 -> null

C 1 -> 2 -> 5 -> 9 -> null

D 1 -> 5 -> 2 -> 9 -> null

💡 Hint

Trace how merge sort splits and merges the array step by step.

Merge sort splits the array into halves recursively and merges them in sorted order. The final sorted array is 1, 2, 5, 9.

🧠 Conceptual

intermediate

Understanding the divide step in merge sort

In merge sort, what is the main purpose of the 'divide' step?

A To split the array into smaller parts until each part has one element

B To merge two sorted arrays into one sorted array

C To find the maximum element in the array

D To swap elements to sort the array in place

💡 Hint

Think about how merge sort breaks down the problem before sorting.

The divide step breaks the array into smaller parts until each part has one element, which is trivially sorted.

🔧 Debug

advanced

Identify the error in this merge function

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

DSA C#

void Merge(int[] arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int[] L = new int[n1];
    int[] R = new int[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 iIndex = 0, jIndex = 0, k = l;
    while (iIndex < n1 && jIndex < n2) {
        if (L[iIndex] <= R[jIndex]) {
            arr[k] = L[iIndex];
            iIndex++;
        } else {
            arr[k] = R[jIndex];
            jIndex++;
        }
        k++;
    }
    while (iIndex < n1) {
        arr[k] = L[iIndex];
        iIndex++;
        k++;
    }
    while (jIndex < n2) {
        arr[k] = R[jIndex];
        jIndex++;
        k++;
    }
}

A NullReferenceException because arrays are not initialized

B IndexOutOfRangeException due to loop going out of bounds

C No error, code runs correctly

D StackOverflowException due to infinite recursion

💡 Hint

Check the for loop conditions carefully for array indexing.

The for loop 'for (int i = 0; i <= n1; i++)' accesses L[i] where i can be n1, which is out of bounds since L has size n1.

❓ Predict Output

advanced

Result of merge sort on a reversed array

What is the output after merge sorting this reversed array?

DSA C#

using System;

class Program {
    static void Merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        int[] L = new int[n1];
        int[] R = new int[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 iIndex = 0, jIndex = 0, k = l;
        while (iIndex < n1 && jIndex < n2) {
            if (L[iIndex] <= R[jIndex]) {
                arr[k] = L[iIndex];
                iIndex++;
            } else {
                arr[k] = R[jIndex];
                jIndex++;
            }
            k++;
        }
        while (iIndex < n1) {
            arr[k] = L[iIndex];
            iIndex++;
            k++;
        }
        while (jIndex < n2) {
            arr[k] = R[jIndex];
            jIndex++;
            k++;
        }
    }

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

    static void Main() {
        int[] arr = {10, 9, 8, 7, 6};
        MergeSort(arr, 0, arr.Length - 1);
        for (int i = 0; i < arr.Length; i++) {
            Console.Write(arr[i]);
            if (i != arr.Length - 1) Console.Write(" -> ");
        }
        Console.WriteLine(" -> null");
    }
}

A 6 -> 7 -> 8 -> 9 -> 10 -> null

B 10 -> 9 -> 8 -> 7 -> 6 -> null

C 7 -> 6 -> 8 -> 9 -> 10 -> null

D 6 -> 8 -> 7 -> 9 -> 10 -> null

💡 Hint

Merge sort always sorts in ascending order by merging sorted halves.

The reversed array is sorted ascending: 6, 7, 8, 9, 10 after merge sort.

🧠 Conceptual

expert

Time complexity of merge sort explained

What is the time complexity of merge sort and why?

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

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

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

D O(n log n) because the array is divided in half log n times and merging takes O(n) each time

💡 Hint

Think about how many times the array is split and how much work merging takes.

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

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