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.

Practice

1. What is the main idea behind the Merge Sort algorithm?

easy

A. Compare each element with every other element and swap if needed

B. Pick the smallest element and place it at the beginning repeatedly

C. Divide the list into halves, sort each half, then merge them

D. Use a pivot to partition the list and sort partitions recursively

Solution

1. Step 1: Understand the divide and conquer approach

   Merge Sort splits the list into two halves recursively until single elements remain.

2. Step 2: Merge sorted halves

   It then merges these halves back together in sorted order.

3. Final Answer:

   Divide the list into halves, sort each half, then merge them -> Option C

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 Merge Sort uses a pivot like Quick Sort
• Believing Merge Sort sorts in place without extra space

2. Which of the following is the correct way to declare a function for merge sort in Go?

easy

A. func mergeSort(arr []int) []int {}

B. func mergeSort(arr int[]) int[] {}

C. func mergeSort(arr array of int) array of int {}

D. func mergeSort(arr []int) int {}

Solution

1. Step 1: Check Go function syntax for slices

   In Go, slices are declared as []int for integer slices.

2. Step 2: Verify return type matches input type

   Merge sort returns a sorted slice, so return type is also []int.

3. Final Answer:

   func mergeSort(arr []int) []int {} -> Option A

4. Quick Check:

   Go slice syntax = []int [OK]

Hint: Go slices use []type syntax, not array of type [OK]

Common Mistakes:

• Using array syntax like int[] which is invalid in Go
• Returning int instead of []int for sorted slice
• Using incorrect parameter types like 'array of int'

3. What will be the output of the following Go code snippet using merge sort?

package main
import "fmt"

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)
}

func merge(left, right []int) []int {
    result := []int{}
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] < right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}

func main() {
    arr := []int{5, 3, 8, 4, 2}
    sorted := mergeSort(arr)
    fmt.Println(sorted)
}

medium

A. [5 3 8 4 2]

B. [2 3 4 5 8]

C. [8 5 4 3 2]

D. [2 3 5 4 8]

Solution

1. Step 1: Trace the recursive splitting

   The array splits into halves until single elements: [5,3,8,4,2] -> [5,3] and [8,4,2], then further splits.

2. Step 2: Merge sorted halves step-by-step

   Merge [5] and [3] -> [3,5]; merge [8] and [4,2] -> [2,4,8]; finally merge [3,5] and [2,4,8] -> [2,3,4,5,8].

3. Final Answer:

   [2 3 4 5 8] -> Option B

4. Quick Check:

   Sorted array = [2 3 4 5 8] [OK]

Hint: Merge halves sorted individually to get full sorted array [OK]

Common Mistakes:

• Assuming original array prints without sorting
• Mixing up merge order causing wrong output
• Forgetting to append remaining elements after loop

4. Identify the bug in this merge function snippet and select the fix:

func merge(left, right []int) []int {
    result := []int{}
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    result = append(result, left[i:]...)
    result = append(result, right[i:]...)
    return result
}

medium

A. Remove the last two append statements

B. Change comparison from <= to <

C. Initialize result with length of left + right

D. Change last append from right[i:] to right[j:]

Solution

1. Step 1: Analyze the append of remaining elements

   After merging common parts, remaining elements from left[i:] and right[j:] must be appended.

2. Step 2: Spot the incorrect slice used

   The code incorrectly appends right[i:] instead of right[j:], which can cause wrong elements or panic.

3. Final Answer:

   Change last append from right[i:] to right[j:] -> Option D

4. Quick Check:

   Append remaining right elements using j index [OK]

Hint: Use correct index variable when appending leftover elements [OK]

Common Mistakes:

• Using wrong index variable for right slice leftover
• Removing leftover appends causing incomplete merge
• Changing comparison operator unnecessarily

5. You want to sort a large list of 1 million integers using merge sort in Go. Which approach is best to optimize memory usage and performance?

hard

A. Use a bottom-up iterative merge sort to avoid deep recursion

B. Use recursive merge sort with slices copied at each step

C. Use merge sort but create new slices for every merge step

D. Use bubble sort instead for simplicity

Solution

1. Step 1: Understand recursion overhead in large data

   Recursive merge sort can cause deep call stacks and many slice copies, increasing memory use.

2. Step 2: Bottom-up iterative merge sort reduces recursion

   Bottom-up merge sort merges pairs iteratively, reducing recursion and memory overhead.

3. Final Answer:

   Use a bottom-up iterative merge sort to avoid deep recursion -> Option A

4. Quick Check:

   Iterative merge sort = better memory for large data [OK]

Hint: Iterative merge sort saves stack and memory for big lists [OK]

Common Mistakes:

• Ignoring recursion limits on large inputs
• Copying slices unnecessarily increasing memory
• Choosing inefficient sorts like bubble sort for big data