Merge Sort Algorithm in DSA Go - Execution Trace

Concept Flow - Merge Sort Algorithm

Start: Full array

↓

Divide array into halves

↓

Recursively sort left half

→Recursively sort right half

↓

Merge two sorted halves

↓

Sorted array

↓

Done

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

Execution Sample

DSA Go

func mergeSort(arr []int) []int {
  if len(arr) <= 1 {
    return arr
  }
  mid := len(arr)/2
  left := mergeSort(arr[:mid])
  right := mergeSort(arr[mid:])
  return merge(left, right)
}

This code recursively splits the array, sorts each half, and merges them into a sorted array.

Execution Table

Step	Operation	Array State	Subarrays Divided	Merge Action	Resulting Array
1	Start	[38, 27, 43, 3, 9, 82, 10]	[38, 27, 43, 3] and [9, 82, 10]	None	[38, 27, 43, 3, 9, 82, 10]
2	Divide Left Half	[38, 27, 43, 3]	[38, 27] and [43, 3]	None	[38, 27, 43, 3]
3	Divide Left-Left	[38, 27]	[38] and [27]	None	[38, 27]
4	Merge Left-Left	N/A	N/A	Merge [38] and [27]	[27, 38]
5	Divide Left-Right	[43, 3]	[43] and [3]	None	[43, 3]
6	Merge Left-Right	N/A	N/A	Merge [43] and [3]	[3, 43]
7	Merge Left Half	N/A	N/A	Merge [27, 38] and [3, 43]	[3, 27, 38, 43]
8	Divide Right Half	[9, 82, 10]	[9] and [82, 10]	None	[9, 82, 10]
9	Divide Right-Right	[82, 10]	[82] and [10]	None	[82, 10]
10	Merge Right-Right	N/A	N/A	Merge [82] and [10]	[10, 82]
11	Merge Right Half	N/A	N/A	Merge [9] and [10, 82]	[9, 10, 82]
12	Merge Full Array	N/A	N/A	Merge [3, 27, 38, 43] and [9, 10, 82]	[3, 9, 10, 27, 38, 43, 82]
13	Done	[3, 9, 10, 27, 38, 43, 82]	N/A	N/A	[3, 9, 10, 27, 38, 43, 82]

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

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 7	After Step 10	After Step 11	Final
arr	[38, 27, 43, 3, 9, 82, 10]	[27, 38]	[3, 43]	[3, 27, 38, 43]	[10, 82]	[9, 10, 82]	[3, 9, 10, 27, 38, 43, 82]
left	N/A	[27, 38]	[3, 43]	[3, 27, 38, 43]	N/A	N/A	[3, 27, 38, 43]
right	N/A	N/A	N/A	N/A	[10, 82]	[9, 10, 82]	[9, 10, 82]
mid	N/A	2	2	4	2	1	3

Key Moments - 3 Insights

Why do we stop dividing when the subarray length is 1?

Because a single element is already sorted, as shown in steps 3 and 5 where arrays [38] and [27] are not divided further.

How does the merge step combine two sorted arrays?

It compares elements from both arrays and picks the smaller one step-by-step, as seen in steps 4, 6, and 7 where merging produces sorted arrays like [27, 38] and [3, 43].

Why do we need to keep track of 'mid' during recursion?

The 'mid' index divides the array into halves for recursive sorting, as shown in variable_tracker where 'mid' changes to split arrays correctly at each step.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the resulting array after merging?

A [27, 38, 3, 43]

B [3, 27, 38, 43]

C [38, 27, 43, 3]

D [3, 43, 27, 38]

💡 Hint

Check the 'Resulting Array' column at step 7 in the execution_table.

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

A Step 9

B Step 10

C Step 11

D Step 12

💡 Hint

Look at the 'Merge Action' and 'Resulting Array' columns for the right half in the execution_table.

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

A Merge steps would still occur but no swaps needed

B Merge steps would be skipped

C Array would be reversed

D Algorithm would fail

💡 Hint

Merge Sort always merges subarrays; see steps 4 and 6 where merging happens regardless of order.

Concept Snapshot

Merge Sort Algorithm:
- Recursively split array into halves
- Base case: single element arrays
- Merge two sorted halves by comparing elements
- Time complexity: O(n log n)
- 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 recursion to split and merge. Each merge compares elements from two sorted subarrays and combines them into one sorted array. This continues until the whole array is sorted. The key steps are dividing, sorting subarrays, and merging. The algorithm is efficient and stable, making it useful for large datasets.