Merge Sort as Divide and Conquer in DSA C# - Execution Trace

Concept Flow - Merge Sort as Divide and Conquer

Start with full array

↓

Divide array into two halves

↓

Recursively sort left half

→Recursively sort right half

↓

Merge two sorted halves into one sorted array

↓

Return sorted array

↓

Done

Merge Sort splits the array into halves recursively, sorts each half, then merges them back in order.

Execution Sample

DSA C#

int[] MergeSort(int[] arr) {
  if (arr.Length <= 1) return arr;
  int mid = arr.Length / 2;
  var left = MergeSort(arr[..mid]);
  var right = MergeSort(arr[mid..]);
  return Merge(left, right);
}

This code splits the array until single elements, then merges sorted halves back.

Execution Table

Step	Operation	Array Segment	Action Detail	Resulting Array State
1	Start	[38, 27, 43, 3, 9, 82, 10]	Full array to sort	[38, 27, 43, 3, 9, 82, 10]
2	Divide	[38, 27, 43, 3, 9, 82, 10]	Split into left [38,27,43] and right [3,9,82,10]	[38, 27, 43, 3, 9, 82, 10]
3	Divide	[38, 27, 43]	Split into left [38] and right [27,43]	[38, 27, 43, 3, 9, 82, 10]
4	Divide	[27, 43]	Split into left [27] and right [43]	[38, 27, 43, 3, 9, 82, 10]
5	Merge	[27] and [43]	Merge sorted arrays	[38, 27, 43, 3, 9, 82, 10] → [27, 43]
6	Merge	[38] and [27, 43]	Merge sorted arrays	[27, 38, 43, 3, 9, 82, 10]
7	Divide	[3, 9, 82, 10]	Split into left [3,9] and right [82,10]	[27, 38, 43, 3, 9, 82, 10]
8	Divide	[3, 9]	Split into left [3] and right [9]	[27, 38, 43, 3, 9, 82, 10]
9	Merge	[3] and [9]	Merge sorted arrays	[27, 38, 43, 3, 9, 82, 10] → [3, 9]
10	Divide	[82, 10]	Split into left [82] and right [10]	[27, 38, 43, 3, 9, 82, 10]
11	Merge	[82] and [10]	Merge sorted arrays	[27, 38, 43, 3, 9, 82, 10] → [10, 82]
12	Merge	[3, 9] and [10, 82]	Merge sorted arrays	[27, 38, 43, 3, 9, 10, 82]
13	Merge	[27, 38, 43] and [3, 9, 10, 82]	Merge sorted arrays	[3, 9, 10, 27, 38, 43, 82]
14	Done	[3, 9, 10, 27, 38, 43, 82]	Fully sorted array	[3, 9, 10, 27, 38, 43, 82]

💡 All subarrays reduced to single elements and merged back fully sorted.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 6	After Step 9	After Step 11	After Step 12	After Step 13	Final
arr	[38, 27, 43, 3, 9, 82, 10]	[38, 27, 43]	[27, 43]	[27, 38, 43]	[3, 9]	[10, 82]	[3, 9, 10, 82]	[27, 38, 43]	[3, 9, 10, 27, 38, 43, 82]
left	N/A	[38, 27, 43]	[38]	[38]	[3, 9]	[82]	[3, 9, 10, 82]	[27, 38, 43]	[3, 9, 10, 27, 38, 43, 82]
right	N/A	[3, 9, 82, 10]	[27, 43]	[27, 43]	[9]	[10]	[10, 82]	[3, 9, 10, 82]	[3, 9, 10, 27, 38, 43, 82]

Key Moments - 3 Insights

Why do we split the array until single elements before merging?

Because single elements are naturally sorted, merging them step-by-step builds sorted larger arrays. See steps 3 to 5 where [27] and [43] merge.

How does merging two sorted arrays keep the result sorted?

We compare the smallest elements of each array and pick the smaller one first, ensuring order. See step 6 merging [38] and [27, 43] into [27, 38, 43].

Why do we merge back after sorting both halves?

Because sorting halves separately doesn't sort the whole array. Merging combines sorted halves into a fully sorted array. See step 13 merging [27, 38, 43] and [3, 9, 10, 82].

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after step 6?

A [38, 27, 43, 3, 9, 82, 10]

B [27, 38, 43, 3, 9, 82, 10]

C ]01 ,28 ,9 ,3 ,34 ,83 ,72[

D [3, 9, 10, 27, 38, 43, 82]

💡 Hint

Check the 'Resulting Array State' column at step 6 in the execution table.

At which step does the right half [3, 9, 10, 82] become fully merged and sorted?

A Step 9

B Step 11

C Step 12

D Step 13

💡 Hint

Look for the merge operation combining [3, 9] and [10, 82] in the execution table.

If the initial array had only one element, what would happen in the execution table?

A It would immediately return the array without dividing.

B It would try to divide but fail.

C It would merge with an empty array.

D It would cause an error.

💡 Hint

Refer to the base case in the code sample where array length <= 1 returns immediately.

Concept Snapshot

Merge Sort splits array into halves recursively.
Sorts each half separately.
Merges sorted halves back into one sorted array.
Uses divide and conquer approach.
Runs in O(n log n) time.

Full Transcript

Merge Sort works by dividing the array into two halves repeatedly until each subarray has one element. Single elements are naturally sorted. Then, it merges these small sorted arrays step-by-step to form larger sorted arrays. This merging compares elements from each half and picks the smaller one first to keep order. The process continues until the entire array is merged back sorted. The code uses recursion to split and merge. The base case returns the array if it has one or zero elements. This method is efficient and stable, running 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