Merge Sort Algorithm in DSA C# - Execution Trace

Concept Flow - Merge Sort Algorithm

Start with full array

↓

Divide array into two halves

↓

Recursively apply merge sort on left half

↓

Base case: single element or empty

↓

Merge two sorted halves

↓

Sorted array

↓

Done

Merge Sort divides the array into halves recursively until single elements remain, then merges these sorted halves back together.

Execution Sample

DSA C#

void MergeSort(int[] arr, int left, int right) {
  if (left < right) {
    int mid = (left + right) / 2;
    MergeSort(arr, left, mid);
    MergeSort(arr, mid + 1, right);
    Merge(arr, left, mid, right);
  }
}

This code recursively splits the array and merges sorted halves.

Execution Table

Step	Operation	Array Segment	Action Detail	Visual State
1	Split	[38, 27, 43, 3, 9, 82, 10]	Divide into [38,27,43,3] and [9,82,10]	[38, 27, 43, 3, 9, 82, 10]
2	Split	[38, 27, 43, 3]	Divide into [38,27] and [43,3]	[38, 27, 43, 3, 9, 82, 10]
3	Split	[38, 27]	Divide into [38] and [27]	[38, 27, 43, 3, 9, 82, 10]
4	Base case	[38]	Single element, no split	[38, 27, 43, 3, 9, 82, 10]
5	Base case	[27]	Single element, no split	[38, 27, 43, 3, 9, 82, 10]
6	Merge	[38, 27]	Merge [38] and [27] into [27, 38]	[27, 38, 43, 3, 9, 82, 10]
7	Split	[43, 3]	Divide into [43] and [3]	[27, 38, 43, 3, 9, 82, 10]
8	Base case	[43]	Single element, no split	[27, 38, 43, 3, 9, 82, 10]
9	Base case	[3]	Single element, no split	[27, 38, 43, 3, 9, 82, 10]
10	Merge	[43, 3]	Merge [43] and [3] into [3, 43]	[27, 38, 3, 43, 9, 82, 10]
11	Merge	[27, 38, 3, 43]	Merge [27,38] and [3,43] into [3, 27, 38, 43]	[3, 27, 38, 43, 9, 82, 10]
12	Split	[9, 82, 10]	Divide into [9,82] and [10]	[3, 27, 38, 43, 9, 82, 10]
13	Split	[9, 82]	Divide into [9] and [82]	[3, 27, 38, 43, 9, 82, 10]
14	Base case	[9]	Single element, no split	[3, 27, 38, 43, 9, 82, 10]
15	Base case	[82]	Single element, no split	[3, 27, 38, 43, 9, 82, 10]
16	Merge	[9, 82]	Merge [9] and [82] into [9, 82]	[3, 27, 38, 43, 9, 82, 10]
17	Base case	[10]	Single element, no split	[3, 27, 38, 43, 9, 82, 10]
18	Merge	[9, 82, 10]	Merge [9,82] and [10] into [9, 10, 82]	[3, 27, 38, 43, 9, 10, 82]
19	Merge	[3, 27, 38, 43, 9, 10, 82]	Merge [3,27,38,43] and [9,10,82] into [3, 9, 10, 27, 38, 43, 82]	[3, 9, 10, 27, 38, 43, 82]
20	Done	[3, 9, 10, 27, 38, 43, 82]	Array fully sorted	[3, 9, 10, 27, 38, 43, 82]

💡 All segments reduced to single elements and merged back into a fully sorted array

Variable Tracker

Variable	Start	After Step 6	After Step 10	After Step 11	After Step 18	After Step 19	Final
Array	[38, 27, 43, 3, 9, 82, 10]	[27, 38, 43, 3, 9, 82, 10]	[27, 38, 3, 43, 9, 82, 10]	[3, 27, 38, 43, 9, 82, 10]	[3, 27, 38, 43, 9, 10, 82]	[3, 9, 10, 27, 38, 43, 82]	[3, 9, 10, 27, 38, 43, 82]
Left Index	0	0	0	0	4	0	0
Right Index	6	1	3	3	6	6	6
Mid Index	3	0	1	1	5	3	3

Key Moments - 3 Insights

Why do we stop splitting when the segment has only one element?

Because a single element is already sorted by itself, so no further splitting is needed. See execution_table rows 4,5,8,9,14,15,17 where base cases occur.

How does the merge step combine two sorted halves correctly?

It compares the smallest elements of each half and picks the smaller one step-by-step, building a sorted merged array. Refer to execution_table rows 6,10,11,16,18,19 showing merges.

Why do we need to keep track of left, mid, and right indices?

These indices define the current segment boundaries for splitting and merging. Without them, we can't know which part of the array to process. See variable_tracker for how these change.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the array state after merging [38] and [27]?

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

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

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

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

💡 Hint

Check the Visual State column in execution_table row 6.

At which step does the array segment [9, 82, 10] get fully merged into a sorted segment?

A Step 18

B Step 16

C Step 19

D Step 20

💡 Hint

Look for the merge operation on [9, 82, 10] in execution_table rows.

If the initial array was already sorted, how would the merge steps change?

A No merges would happen

B Merge steps would still happen but no swaps needed

C Splitting would not happen

D The array would be reversed

💡 Hint

Merging always happens to combine halves, but if sorted, elements are picked without swaps.

Concept Snapshot

Merge Sort Algorithm:
- Recursively split array into halves until single elements
- Merge sorted halves by comparing elements
- Time complexity: O(n log n)
- Uses extra space for merging
- Stable and efficient for large data

Full Transcript

Merge Sort works by dividing the array into smaller parts until each part has one element. Then it merges these parts back together in sorted order. The process uses left, mid, and right indices to track segments. Base cases occur when segments have one element. Merging compares elements from two halves and builds a sorted array. This continues until the whole array is sorted. The execution table shows each split and merge step with the array state. Variable tracker shows how indices and array change. Key moments clarify why splitting stops at one element, how merging works, and the role of indices. The quiz tests understanding of array states after merges and behavior if array is already sorted.

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