Merge Sort as Divide and Conquer in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the 'Divide and Conquer' approach in Merge Sort?

Divide the list into smaller parts, sort each part, then combine them back together in order.

beginner

In Merge Sort, what happens after dividing the array into two halves?

Each half is sorted recursively using Merge Sort before merging them back.

intermediate

Why is Merge Sort considered efficient for large lists?

Because it breaks the problem into smaller parts and merges sorted parts efficiently, running in O(n log n) time.

beginner

What is the role of the 'merge' step in Merge Sort?

To combine two sorted lists into one sorted list by comparing elements one by one.

beginner

Show the base case condition in Merge Sort recursion.

When the list has one or zero elements, it is already sorted, so recursion stops.

What is the first step in Merge Sort?

A Merge two sorted lists

B Divide the list into two halves

C Sort the entire list directly

D Swap the first and last elements

Merge Sort starts by dividing the list into two halves before sorting.

What is the time complexity of Merge Sort?

A O(n log n)

B O(n^2)

C O(log n)

D O(n)

Merge Sort runs in O(n log n) time due to dividing and merging steps.

What does the 'merge' function do in Merge Sort?

A Splits the list into halves

B Finds the middle element

C Combines two sorted lists into one sorted list

D Removes duplicates from the list

The merge function combines two sorted lists into a single sorted list.

When does the recursion stop in Merge Sort?

A When the list has one or zero elements

B When the list is empty

C After the first split

D When the list is fully merged

Recursion stops when the list is small enough (one or zero elements) to be considered sorted.

Which of these is NOT a characteristic of Merge Sort?

A Has O(n log n) time complexity

B Stable sorting algorithm

C Uses divide and conquer approach

D In-place sorting without extra space

Merge Sort requires extra space for merging, so it is not in-place.

Explain how Merge Sort uses the divide and conquer strategy to sort a list.

Think about breaking the problem into smaller parts and then combining results.

Describe the merge step in Merge Sort and why it is important.

Focus on how two sorted parts become one sorted whole.

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