Merge Sort as Divide and Conquer in DSA Go - Time & Space Complexity

Time Complexity: Merge Sort as Divide and Conquer

O(n log n)

Understanding Time Complexity

We want to understand how the time taken by merge sort changes as the list size grows.

How does breaking the list and merging affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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
}

This code splits the list into halves, sorts each half recursively, then merges them back in order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive splitting and merging of sublists.
• How many times: The list is split until single elements remain (log n times), and merging happens at each level over all elements (n times per level).

How Execution Grows With Input

Each time we split, the number of sublists doubles but their size halves. Merging all sublists at one level takes time proportional to n.

Input Size (n)	Approx. Operations
10	About 10 * 4 = 40 (4 levels of splitting)
100	About 100 * 7 = 700 (7 levels)
1000	About 1000 * 10 = 10,000 (10 levels)

Pattern observation: Operations grow roughly as n times log n, meaning doubling input size adds a bit more than double the work.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than linearly but much slower than quadratic, making merge sort efficient for large lists.

Common Mistake

[X] Wrong: "Merge sort is just like bubble sort and takes quadratic time because it compares elements repeatedly."

[OK] Correct: Merge sort splits the list to reduce problem size and merges sorted parts efficiently, so it avoids repeated comparisons over the whole list, keeping time lower.

Interview Connect

Understanding merge sort's time complexity shows you can analyze divide and conquer methods, a key skill for solving many problems efficiently.

Self-Check

"What if we changed the merge step to use a different method that takes longer? How would the time complexity change?"

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