Merge Sort as Divide and Conquer in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Merge Sort on a small array

What is the output of the following Go code that uses merge sort to sort an array?

DSA Go

package main
import "fmt"

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 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 main() {
    arr := []int{5, 3, 8, 4, 2}
    sorted := mergeSort(arr)
    fmt.Println(sorted)
}

A [8 5 4 3 2]

B [5 3 8 4 2]

C [2 4 3 5 8]

D [2 3 4 5 8]

💡 Hint

Trace how merge sort splits the array and merges sorted halves.

The merge sort splits the array recursively until single elements remain, then merges them in sorted order. The final sorted array is [2 3 4 5 8].

🧠 Conceptual

intermediate

Understanding the divide step in merge sort

In merge sort, what does the 'divide' step do to the input array?

A Merges two sorted arrays into one sorted array

B Splits the array into two halves until each sub-array has one element

C Sorts the entire array in one pass

D Removes duplicate elements from the array

💡 Hint

Think about how merge sort breaks down the problem before sorting.

The divide step splits the array into smaller parts until each part has only one element, which is trivially sorted.

🔧 Debug

advanced

Identify the error in this merge function

What error will occur when running this merge function in Go?

DSA Go

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
}

A runtime error: index out of range

B compilation error: missing return statement

C no error, returns correct merged slice

D runtime error: nil pointer dereference

💡 Hint

Check the loop condition and how indexes i and j are used.

The loop condition uses <= which allows i or j to equal the length of the slice, causing index out of range when accessing left[i] or right[j].

🚀 Application

advanced

Merge Sort Stability Check

Given the following array of structs sorted by 'value' using merge sort, which output shows that merge sort is stable (preserves order of equal elements)?

DSA Go

type Item struct {
    value int
    id    int
}

func merge(left, right []Item) []Item {
    result := []Item{}
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i].value <= right[j].value {
            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 mergeSort(arr []Item) []Item {
    if len(arr) <= 1 {
        return arr
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}

func main() {
    arr := []Item{{2,1}, {3,2}, {2,3}, {1,4}}
    sorted := mergeSort(arr)
    for _, v := range sorted {
        fmt.Printf("{value:%d, id:%d} ", v.value, v.id)
    }
}

A {value:1, id:4} {value:2, id:1} {value:2, id:3} {value:3, id:2}

B {value:1, id:4} {value:2, id:3} {value:2, id:1} {value:3, id:2}

C {value:1, id:4} {value:3, id:2} {value:2, id:1} {value:2, id:3}

D {value:3, id:2} {value:2, id:1} {value:2, id:3} {value:1, id:4}

💡 Hint

Stability means equal values keep their original order by id.

Merge sort is stable because it uses <= in comparison, so items with equal values keep their original order. Option A shows this order preserved.

🧠 Conceptual

expert

Time Complexity of Merge Sort

What is the time complexity of merge sort and why?

A O(n^2) because each element is compared with every other element

B O(log n) because it only divides the array without merging

C O(n log n) because the array is divided in half log n times and merging takes O(n) each time

D O(n) because it sorts the array in a single pass

💡 Hint

Consider how many times the array is split and how merging works.

Merge sort divides the array into halves log n times and merges all elements each level in O(n), resulting in O(n log n) time complexity.

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