Merge Sort as Divide and Conquer in DSA Go

Mental Model

Split the list into smaller parts, sort each part, then join them back in order.

Analogy: Imagine sorting a big pile of cards by splitting them into smaller piles, sorting each small pile, then carefully merging them back into one sorted pile.

Unsorted list:
[38, 27, 43, 3, 9, 82, 10]

Split into halves:
[38, 27, 43]   [3, 9, 82, 10]

Split again:
[38] [27, 43]   [3, 9] [82, 10]

Split until single elements:
[38] [27] [43]   [3] [9] [82] [10]

Dry Run Walkthrough

Input: list: [38, 27, 43, 3, 9, 82, 10]

Goal: Sort the list in ascending order using merge sort

Step 1: Split list into two halves: left=[38,27,43], right=[3,9,82,10]

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

Why: Divide the problem into smaller parts to sort them separately

Step 2: Split left half into [38] and [27,43]

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

Why: Keep dividing until sublists have one element

Step 3: Split [27,43] into [27] and [43]

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

Why: Single elements are considered sorted

Step 4: Merge [27] and [43] into sorted [27,43]

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

Why: Combine two sorted lists into one sorted list

Step 5: Merge [38] and [27,43] into sorted [27,38,43]

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

Why: Merge sorted sublists to form larger sorted list

Step 6: Split right half [3,9,82,10] into [3,9] and [82,10]

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

Why: Divide right half further for sorting

Step 7: Split [3,9] into [3] and [9]

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

Why: Single elements are sorted

Step 8: Merge [3] and [9] into sorted [3,9]

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

Why: Merge sorted sublists

Step 9: Split [82,10] into [82] and [10]

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

Why: Divide until single elements

Step 10: Merge [82] and [10] into sorted [10,82]

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

Why: Merge sorted sublists

Step 11: Merge [3,9] and [10,82] into sorted [3,9,10,82]

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

Why: Merge sorted halves

Step 12: Merge [27,38,43] and [3,9,10,82] into fully sorted [3,9,10,27,38,43,82]

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

Why: Final merge to get fully sorted list

Result:

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

Annotated Code

DSA Go

package main

import "fmt"

// merge merges two sorted slices into one sorted slice
func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++ // advance i to next element in left
        } else {
            result = append(result, right[j])
            j++ // advance j to next element in right
        }
    }
    // append remaining elements from left
    result = append(result, left[i:]...)
    // append remaining elements from right
    result = append(result, right[j:]...)
    return result
}

// mergeSort recursively sorts the slice using divide and conquer
func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr // base case: single element is sorted
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])   // sort left half
    right := mergeSort(arr[mid:])  // sort right half
    return merge(left, right)      // merge sorted halves
}

func main() {
    arr := []int{38, 27, 43, 3, 9, 82, 10}
    sorted := mergeSort(arr)
    fmt.Println(sorted)
}

if len(arr) <= 1 { return arr // base case: single element is sorted }

stop dividing when sublist has one or zero elements

mid := len(arr) / 2

find middle index to split list

left := mergeSort(arr[:mid]) // sort left half right := mergeSort(arr[mid:]) // sort right half

recursively sort left and right halves

return merge(left, right) // merge sorted halves

combine two sorted halves into one sorted list

for i < len(left) && j < len(right) { if left[i] <= right[j] { result = append(result, left[i]) i++ // advance i to next element in left } else { result = append(result, right[j]) j++ // advance j to next element in right } }

merge elements by comparing heads of left and right

result = append(result, left[i:]...) result = append(result, right[j:]...)

append any remaining elements after one list is exhausted

Output

[3 9 10 27 38 43 82]

Complexity Analysis

Time: O(n log n) because the list is repeatedly split in half (log n splits) and merging takes linear time at each level

Space: O(n) because extra space is needed to hold merged lists during the process

vs Alternative: Compared to simple sorting like bubble sort O(n²), merge sort is much faster for large lists due to divide and conquer

Edge Cases

empty list

returns empty list immediately without error

DSA Go

if len(arr) <= 1 {
        return arr // base case: single element is sorted
    }

single element list

returns the single element list as is

DSA Go

if len(arr) <= 1 {
        return arr // base case: single element is sorted
    }

list with duplicate elements

duplicates are preserved and sorted correctly

DSA Go

if left[i] <= right[j] {

When to Use This Pattern

When you see a problem asking to sort or organize data efficiently, especially large lists, reach for merge sort because it splits the problem into smaller parts and merges them back sorted.

Common Mistakes

Mistake: Not handling the base case correctly, causing infinite recursion
Fix: Add a condition to return when the list has one or zero elements

Mistake: Merging without comparing elements properly, leading to unsorted output
Fix: Compare elements from left and right lists and append the smaller one first

Summary

It sorts a list by splitting it into smaller parts, sorting those, and merging them back.

Use it when you need a reliable and efficient sorting method for large lists.

The key insight is dividing the problem into smaller sorted pieces and merging them carefully.

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