Merge Sort Algorithm in DSA C++ - Execution Trace

Concept Flow - Merge Sort Algorithm

Start: Full array

↓

Divide array into two halves

↓

Recursively apply merge sort on left half

↓

Merge two sorted halves

↓

Sorted array

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

Execution Sample

DSA C++

void mergeSort(int arr[], int left, int right) {
  if (left < right) {
    int mid = left + (right - left) / 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 State	Sub-array Sorted	Merge Action	Visual State
1	Split full array [38, 27, 43, 3, 9, 82, 10]	[38, 27, 43, 3, 9, 82, 10]	No	Split into [38,27,43,3] and [9,82,10]	[38,27,43,3] | [9,82,10]
2	Split left half [38,27,43,3]	[38, 27, 43, 3, 9, 82, 10]	No	Split into [38,27] and [43,3]	[38,27] | [43,3] | [9,82,10]
3	Split left-left [38,27]	[38, 27, 43, 3, 9, 82, 10]	No	Split into [38] and [27]	[38] | [27] | [43,3] | [9,82,10]
4	Merge [38] and [27]	[27, 38, 43, 3, 9, 82, 10]	Yes	Compare 38 and 27, merge to [27,38]	[27,38] | [43,3] | [9,82,10]
5	Split left-right [43,3]	[27, 38, 43, 3, 9, 82, 10]	No	Split into [43] and [3]	[27,38] | [43] | [3] | [9,82,10]
6	Merge [43] and [3]	[27, 38, 3, 43, 9, 82, 10]	Yes	Compare 43 and 3, merge to [3,43]	[27,38] | [3,43] | [9,82,10]
7	Merge [27,38] and [3,43]	[3, 27, 38, 43, 9, 82, 10]	Yes	Merge sorted halves to [3,27,38,43]	[3,27,38,43] | [9,82,10]
8	Split right half [9,82,10]	[3, 27, 38, 43, 9, 82, 10]	No	Split into [9,82] and [10]	[3,27,38,43] | [9,82] | [10]
9	Split right-left [9,82]	[3, 27, 38, 43, 9, 82, 10]	No	Split into [9] and [82]	[3,27,38,43] | [9] | [82] | [10]
10	Merge [9] and [82]	[3, 27, 38, 43, 9, 82, 10]	Yes	Merge to [9,82]	[3,27,38,43] | [9,82] | [10]
11	Merge [9,82] and [10]	[3, 27, 38, 43, 9, 10, 82]	Yes	Merge to [9,10,82]	[3,27,38,43] | [9,10,82]
12	Merge [3,27,38,43] and [9,10,82]	[3, 9, 10, 27, 38, 43, 82]	Yes	Final merge to [3,9,10,27,38,43,82]	[3,9,10,27,38,43,82]
13	End	[3, 9, 10, 27, 38, 43, 82]	Yes	Array fully sorted	[3,9,10,27,38,43,82]

💡 All sub-arrays merged and sorted, full array sorted.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 7	After Step 10	After Step 11	After Step 12	Final
Array State	[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, 82, 10]	[3, 27, 38, 43, 9, 10, 82]	[3, 9, 10, 27, 38, 43, 82]	[3, 9, 10, 27, 38, 43, 82]
Left Sub-array	[38, 27, 43, 3]	[27, 38, 43, 3]	[27, 38, 3, 43]	[3, 27, 38, 43]	[3, 27, 38, 43]	[3, 27, 38, 43]	[3, 27, 38, 43]	[3, 27, 38, 43]
Right Sub-array	[9, 82, 10]	[9, 82, 10]	[9, 82, 10]	[9, 82, 10]	[9, 82, 10]	[9, 10, 82]	[9, 10, 82]	[9, 10, 82]

Key Moments - 3 Insights

Why do we split the array until sub-arrays have only one element?

Because a single element is already sorted, as shown in steps 3 and 5 where arrays like [38] and [27] are the base cases before merging.

How does the merge step combine two sorted sub-arrays?

It compares elements from both sub-arrays and picks the smaller one step-by-step, as seen in steps 4, 6, and 7 where merging happens by comparing and ordering elements.

Why do we merge sorted halves back up the recursion?

Because merging two sorted halves produces a bigger sorted array, building up to the full sorted array, as shown in steps 7, 11, and 12.

Visual Quiz - 3 Questions

Look at the execution table at step 4, what is the array state after merging [38] and [27]?

A [27, 38]

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

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

D [38, 27]

💡 Hint

Check the 'Array State' column at step 4 in the execution_table.

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

A Step 12

B Step 10

C Step 11

D Step 9

💡 Hint

Look for the step where [9,10,82] appears in the 'Array State' column.

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

A Merges would still happen but no swaps needed

B No merges would happen

C Array would be reversed

D Algorithm would stop early

💡 Hint

Merge sort always divides and merges; sorted input means merges happen without swaps.

Concept Snapshot

Merge Sort Algorithm:
- Divide array into halves recursively
- Base case: single element arrays
- Merge two sorted halves by comparing elements
- Time complexity: O(n log n)
- Stable and efficient for large data
- Uses extra space for merging

Full Transcript

Merge Sort works by splitting the array into smaller parts until each part has one element, which is naturally sorted. Then it merges these parts back together in sorted order. The process repeats recursively for left and right halves. Each merge compares elements from two sorted sub-arrays and combines them into a bigger sorted array. This continues until the whole array is sorted. The execution table shows each split and merge step with the array state. Key moments include understanding why splitting stops at one element, how merging works by comparing elements, and why merging builds the sorted array back up. The visual quiz tests understanding of array states at merge steps and behavior on sorted input.