Merge Sort as Divide and Conquer in DSA C# - Build from Scratch

Merge Sort as Divide and Conquer

📖 Scenario: You are helping a librarian organize a list of book IDs in ascending order. The librarian wants to use a smart method that breaks the list into smaller parts, sorts each part, and then combines them back together in order.

🎯 Goal: Build a program that uses the merge sort method to sort a list of integers step-by-step, showing how the list is split and merged back in order.

📋 What You'll Learn

Create an integer array called numbers with the exact values: 38, 27, 43, 3, 9, 82, 10

Create a helper variable mid to find the middle index of the array

Write a method MergeSort that splits the array into halves recursively

Write a method Merge that combines two sorted halves into one sorted array

Print the sorted array after applying merge sort

💡 Why This Matters

🌍 Real World

Sorting large lists efficiently is important in many applications like organizing data, searching quickly, and managing inventories.

💼 Career

Understanding merge sort helps in software development roles where efficient data handling and algorithm optimization are required.

1

Create the initial array

Create an integer array called numbers with these exact values: 38, 27, 43, 3, 9, 82, 10.

DSA C#

# Create the array called numbers with the given values
// Your code here

Hint

Use int[] numbers = { ... }; to create the array with the exact numbers.

2

Find the middle index

Create an integer variable called mid that stores the middle index of the numbers array using numbers.Length / 2.

DSA C#

int[] numbers = {38, 27, 43, 3, 9, 82, 10};
// Create the mid variable to find the middle index
// Your code here

Hint

Use int mid = numbers.Length / 2; to find the middle index.

3

Write the MergeSort and Merge methods

Write a method called MergeSort that takes an integer array arr and sorts it using the merge sort technique. Also write a helper method called Merge that takes two sorted arrays and returns a single sorted array by combining them.

DSA C#

int[] numbers = {38, 27, 43, 3, 9, 82, 10};
int mid = numbers.Length / 2;

// Write the MergeSort method below
// Your code here

Hint

Use recursion in MergeSort to split the array and call Merge to combine sorted halves.

4

Print the sorted array

Call the MergeSort method on the numbers array and print the sorted array elements separated by spaces using Console.WriteLine.

DSA C#

int[] numbers = {38, 27, 43, 3, 9, 82, 10};
int mid = numbers.Length / 2;

int[] MergeSort(int[] arr)
{
    if (arr.Length <= 1)
        return arr;

    int middle = arr.Length / 2;
    int[] left = new int[middle];
    int[] right = new int[arr.Length - middle];

    for (int i = 0; i < middle; i++)
        left[i] = arr[i];
    for (int i = middle; i < arr.Length; i++)
        right[i - middle] = arr[i];

    left = MergeSort(left);
    right = MergeSort(right);

    return Merge(left, right);
}

int[] Merge(int[] left, int[] right)
{
    int[] result = new int[left.Length + right.Length];
    int i = 0, j = 0, k = 0;

    while (i < left.Length && j < right.Length)
    {
        if (left[i] <= right[j])
        {
            result[k++] = left[i++];
        }
        else
        {
            result[k++] = right[j++];
        }
    }

    while (i < left.Length)
        result[k++] = left[i++];

    while (j < right.Length)
        result[k++] = right[j++];

    return result;
}

// Call MergeSort on numbers and print the sorted array
// Your code here

Hint

Call MergeSort(numbers) and print the result using Console.WriteLine(string.Join(" ", sorted)).

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