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 C# code after sorting the array using merge sort?

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 i1 = 0, j1 = 0, k = l;
        while (i1 < n1 && j1 < n2) {
            if (L[i1] <= R[j1]) {
                arr[k++] = L[i1++];
            } else {
                arr[k++] = R[j1++];
            }
        }
        while (i1 < n1) arr[k++] = L[i1++];
        while (j1 < n2) arr[k++] = R[j1++];
    }

    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);
        foreach (int x in arr) Console.Write(x + " ");
    }
}

A 1 5 2 9

B 5 2 9 1

C 1 2 5 9

D 9 5 2 1

💡 Hint

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

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

🧠 Conceptual

intermediate

Understanding merge step in merge sort

During the merge step of merge sort, what is the main purpose of the two temporary arrays used?

A To reverse the array elements before merging

B To hold the left and right halves so they can be merged in sorted order

C To store the original array elements permanently

D To count the number of elements in the array

💡 Hint

Think about how merge sort combines two sorted halves.

The temporary arrays hold the left and right halves so the algorithm can compare and merge them in sorted order.

🔧 Debug

advanced

Identify the error in this merge sort implementation

What error will this code produce when run?

DSA C#

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

A StackOverflowException due to infinite recursion

B No error, code runs correctly

C IndexOutOfRangeException during merge

D NullReferenceException because arr is null

💡 Hint

Check the base condition for recursion carefully.

The base condition should be 'l < r' to stop recursion. Using 'l <= r' causes infinite recursion leading to stack overflow.

❓ Predict Output

advanced

Output after sorting a reversed array

What is the output of this C# code after applying merge sort to 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 i1 = 0, j1 = 0, k = l;
        while (i1 < n1 && j1 < n2) {
            if (L[i1] <= R[j1]) {
                arr[k++] = L[i1++];
            } else {
                arr[k++] = R[j1++];
            }
        }
        while (i1 < n1) arr[k++] = L[i1++];
        while (j1 < n2) arr[k++] = R[j1++];
    }

    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);
        foreach (int x in arr) Console.Write(x + " ");
    }
}

A 6 7 8 9 10

B 10 9 8 7 6

C 7 6 8 9 10

D 6 8 7 9 10

💡 Hint

Merge sort sorts the array in ascending order.

The reversed array is sorted ascending: 6 7 8 9 10.

🧠 Conceptual

expert

Time complexity of merge sort

What is the time complexity of merge sort in the worst case 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 splits the array without merging

D O(n log n) because the array is repeatedly split in half and merged

💡 Hint

Consider how many times the array is split and merged.

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

Practice

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

easy

A. Pick the smallest element and place it at the beginning repeatedly

B. Divide the list into halves, sort each half, then merge them

C. Compare each element with every other element and swap if needed

D. Build a sorted list by inserting elements one by one

Solution

1. Step 1: Understand the divide and conquer approach

   Merge Sort splits the list into two halves recursively until each sublist has one element.

2. Step 2: Merge sorted halves

   Then it merges these small sorted lists back together in order to form a sorted list.

3. Final Answer:

   Divide the list 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 it sorts by swapping adjacent elements
• Believing it sorts by inserting elements one by one

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 start, int end)

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

Solution

1. Step 1: Identify correct parameter types and names

   The merge function typically takes the array and three indices: left, mid, and right to merge two sorted halves.

2. Step 2: Check C# syntax for method declaration

   In C#, arrays are declared as int[] arr and the function returns void because 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: Look for void return and correct parameters [OK]

Common Mistakes:

• Using incorrect return type (int instead of void)
• Wrong parameter types or order
• Using lowercase function names in C#

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 to the array [4, 1, 3, 2]

   Split into [4,1] and [3,2], sort each half to [1,4] and [2,3].

2. Step 2: Merge the two sorted halves

   Merging [1,4] and [2,3] results in [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 halves stepwise to get sorted array [OK]

Common Mistakes:

• Confusing merge order and producing unsorted output
• Not splitting array correctly
• Printing before sorting completes

4. Identify the bug in this Merge Sort merge function snippet:

void Merge(int[] arr, int left, int mid, int right) {
  int n1 = mid - left + 1;
  int n2 = right - mid;
  int[] L = new int[n1];
  int[] R = new int[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];
  // merging logic follows
}

medium

A. Incorrect array sizes for L and R

B. Loop conditions should use < instead of <= to avoid out of bounds

C. Wrong indices used for copying elements

D. Missing return statement in void function

Solution

1. Step 1: Check array size calculations

   The size of the left array should be mid - left + 1 to include the mid element; the right array size is correct as right - mid.

2. Step 2: Analyze loop conditions for copying elements

   Loops should use < to avoid out of bounds errors.

3. Final Answer:

   Incorrect array sizes for L and R -> Option A

4. Quick Check:

   Left array size must be mid - left + 1 [OK]

Hint: Array size for left = mid - left + 1 [OK]

Common Mistakes:

• Using <= causes index out of range errors
• Miscalculating array sizes
• Confusing mid index offsets

5. Given a large dataset with many duplicate values, how can you modify the Merge Sort algorithm to maintain stability (keep duplicates in original order)?

hard

A. Change Merge Sort to Quick Sort for better stability

B. Sort duplicates separately after Merge Sort completes

C. Use a hash set to remove duplicates before sorting

D. When merging, if elements are equal, take element from left subarray first

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps equal elements in the same order as original.

2. Step 2: Modify merge step to preserve order

   When merging, if elements are equal, always pick from the left subarray first to keep original order.

3. Final Answer:

   When merging, if elements are equal, take element from left subarray first -> Option D

4. Quick Check:

   Stable merge = pick left element first on ties [OK]

Hint: Pick left element first when equal during merge [OK]

Common Mistakes:

• Removing duplicates before sorting changes data
• Assuming Quick Sort is stable (it is not)
• Sorting duplicates separately after merge