Merge Sort as Divide and Conquer in DSA Go - Execution Trace

Concept Flow - Merge Sort as Divide and Conquer

Start: Full Array

↓

Divide Array into Two Halves

↓

Recursively Sort Left Half

→Recursively Sort Right Half

↓

Base Case: Single Element or Empty

↓

Merge Two Sorted Halves

↓

Return Merged Sorted Array

↓

Done

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

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 and merges sorted halves to sort the entire array.

Execution Table

Step	Operation	Array Segment	Action Detail	Resulting Array Segment
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] and [3, 9, 82, 10]
3	Divide Left	[38, 27, 43]	Split into [38] and [27,43]	[38] and [27, 43]
4	Base Case Left	[38]	Single element, return as is	[38]
5	Divide Right Left	[27, 43]	Split into [27] and [43]	[27] and [43]
6	Base Case	[27]	Single element, return as is	[27]
7	Base Case	[43]	Single element, return as is	[43]
8	Merge	[27] and [43]	Compare 27 and 43, merge sorted	[27, 43]
9	Merge	[38] and [27, 43]	Compare 38 with 27 and 43, merge sorted	[27, 38, 43]
10	Divide Right	[3, 9, 82, 10]	Split into [3,9] and [82,10]	[3, 9] and [82, 10]
11	Divide Left Right	[3, 9]	Split into [3] and [9]	[3] and [9]
12	Base Case	[3]	Single element, return as is	[3]
13	Base Case	[9]	Single element, return as is	[9]
14	Merge	[3] and [9]	Compare 3 and 9, merge sorted	[3, 9]
15	Divide Right Right	[82, 10]	Split into [82] and [10]	[82] and [10]
16	Base Case	[82]	Single element, return as is	[82]
17	Base Case	[10]	Single element, return as is	[10]
18	Merge	[82] and [10]	Compare 82 and 10, merge sorted	[10, 82]
19	Merge	[3, 9] and [10, 82]	Merge sorted halves	[3, 9, 10, 82]
20	Merge	[27, 38, 43] and [3, 9, 10, 82]	Final merge to sorted array	[3, 9, 10, 27, 38, 43, 82]
21	End	[3, 9, 10, 27, 38, 43, 82]	Sorted array returned	[3, 9, 10, 27, 38, 43, 82]

💡 All subarrays reduced to single elements, merged back to fully sorted array

Variable Tracker

Variable	Start	After Step 3	After Step 9	After Step 19	Final
arr	[38, 27, 43, 3, 9, 82, 10]	[38, 27, 43] and [3, 9, 82, 10]	[27, 38, 43]	[3, 9, 10, 82]	[3, 9, 10, 27, 38, 43, 82]
left	N/A	[38, 27, 43]	[27, 38, 43]	[3, 9, 10, 82]	[3, 9, 10, 27, 38, 43, 82]
right	N/A	[3, 9, 82, 10]	[3, 9, 10, 82]	N/A	N/A
mid	N/A	3	3	2	N/A

Key Moments - 3 Insights

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

Because a single element is already sorted, so the recursion base case returns it directly (see steps 4, 6, 7, 12, 13, 16, 17).

How does the merge step combine two sorted halves correctly?

It compares the first elements of each half and picks the smaller one step by step, building a sorted merged array (see steps 8, 9, 14, 18, 19, 20).

Why do we divide the array into halves instead of smaller parts?

Dividing into halves ensures the recursion depth is minimal and balanced, making the algorithm efficient (see step 2 and subsequent divides).

Visual Quiz - 3 Questions

Look at the execution table, what is the array segment after step 9?

A [3, 9, 10, 82]

B [38, 27, 43]

C [27, 38, 43]

D [10, 82]

💡 Hint

Check the 'Resulting Array Segment' column at step 9 in the execution_table.

At which step does the merge of [3, 9] and [10, 82] happen?

A Step 14

B Step 19

C Step 18

D Step 20

💡 Hint

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

If the initial array had only one element, which step would return it immediately?

A Step 4

B Step 1

C Step 21

D Step 6

💡 Hint

Base case returns single element arrays immediately, see step 4 for example.

Concept Snapshot

Merge Sort splits array into halves recursively
Base case: single element arrays are sorted
Merge step combines two sorted halves by comparing elements
Overall time complexity: O(n log n)
Stable and efficient divide and conquer sorting algorithm

Full Transcript

Merge Sort is a divide and conquer algorithm that splits the array into two halves recursively until each subarray has one element. These single-element arrays are considered sorted. Then, the algorithm merges these sorted halves step-by-step by comparing their elements and building a sorted array. This process continues until the entire array is merged and sorted. The key steps are dividing, base case return, and merging. This method ensures efficient sorting with time complexity O(n log n).

Practice

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

easy

A. Insert elements one by one into a sorted list

B. Sort the list by repeatedly swapping adjacent elements

C. Select a pivot and partition the list around it

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

Solution

1. Step 1: Understand the divide and conquer approach

   Merge Sort splits the list into smaller parts to make sorting easier.

2. Step 2: Combine sorted parts

   After sorting each half, it merges them to get a fully sorted list.

3. Final Answer:

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

4. Quick Check:

   Merge Sort = Divide, Sort, Merge [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 pivot selection with Quick Sort

2. Which of the following is the correct way to declare a recursive mergeSort function signature in Go?

easy

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

B. func mergeSort(arr int) int

C. func mergeSort(arr []int)

D. func mergeSort(arr []int) int

Solution

1. Step 1: Identify input and output types

   Merge Sort takes a slice of integers and returns a sorted slice of integers.

2. Step 2: Match function signature

   Only func mergeSort(arr []int) []int matches input as []int and output as []int.

3. Final Answer:

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

4. Quick Check:

   Input and output are slices of int [OK]

Hint: Function returns sorted slice, so output is []int [OK]

Common Mistakes:

• Using int instead of []int for input or output
• Missing return type for sorted slice
• Confusing parameter types

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

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

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
}

medium

A. [4 3 2 1]

B. [1 3 2 4]

C. [1 2 3 4]

D. [2 1 3 4]

Solution

1. Step 1: Trace recursive splitting

   Array splits into [4,1] and [3,2], then further splits until single elements.

2. Step 2: Merge sorted halves

   Merge combines sorted parts stepwise: [1,4], [2,3], then [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 returns sorted array ascending [OK]

Common Mistakes:

• Confusing merge order causing wrong output
• Forgetting to merge remaining elements
• Incorrect base case handling

4. Identify the bug in this merge function used in merge sort:

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
}

medium

A. Incorrect slice append syntax for left and right remaining elements

B. Wrong comparison operator in if condition

C. Missing initialization of result slice

D. Loop condition should use || instead of &&

Solution

1. Step 1: Check how remaining elements are appended

   The code uses append(result, left[i:]) which appends a slice as one element, not elements.

2. Step 2: Correct append syntax

   It should use append(result, left[i:]...) to append all elements individually.

3. Final Answer:

   Incorrect slice append syntax for left and right remaining elements -> Option A

4. Quick Check:

   Use ... to append slice elements [OK]

Hint: Use ... to append slice elements, not slice itself [OK]

Common Mistakes:

• Appending slice without ... causes nested slices
• Changing comparison operator unnecessarily
• Using || instead of && in loop condition

5. Given a large list of 1 million integers, which of these is the best reason to choose merge sort over bubble sort?

hard

A. Merge sort uses less memory than bubble sort because it sorts in place

B. Merge sort has better average and worst-case time complexity (O(n log n)) than bubble sort (O(n^2))

C. Bubble sort is faster for large lists because it swaps elements directly

D. Merge sort does not require recursion, so it uses less stack space

Solution

1. Step 1: Compare time complexities

   Merge sort runs in O(n log n), which is much faster than bubble sort's O(n^2) for large n.

2. Step 2: Evaluate memory and recursion claims

   Merge sort uses extra memory and recursion; bubble sort is in-place but slow.

3. Final Answer:

   Merge sort has better average and worst-case time complexity (O(n log n)) than bubble sort (O(n^2)) -> Option B

4. Quick Check:

   Time complexity matters most for large lists [OK]

Hint: Choose O(n log n) over O(n^2) for big data [OK]

Common Mistakes:

• Assuming bubble sort is faster for large data
• Thinking merge sort is in-place
• Ignoring recursion stack usage