Merge Sort Algorithm 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 implements merge sort on the array [4, 1, 3, 2]?

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{4, 1, 3, 2}
    sorted := mergeSort(arr)
    fmt.Println(sorted)
}

A [1 3 2 4]

B [4 3 2 1]

C [1 2 3 4]

D [2 1 3 4]

💡 Hint

Think about how merge sort splits the array and merges sorted halves.

Merge sort splits the array into halves recursively until single elements remain, then merges them back in sorted order. The final sorted array is [1 2 3 4].

🧠 Conceptual

intermediate

Time Complexity of Merge Sort

What is the time complexity of the merge sort algorithm in the average and worst cases?

A O(log n)

B O(n log n)

C O(n^2)

D O(n)

💡 Hint

Consider how many times the array is split and merged.

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

🔧 Debug

advanced

Identify the bug 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 infinite loop

D no error, runs correctly

💡 Hint

Check the loop condition and array indexing carefully.

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

🚀 Application

advanced

Merge Sort on Linked List

Which of the following statements about applying merge sort to a singly linked list is TRUE?

A Merge sort cannot be applied to linked lists.

B Merge sort is inefficient on linked lists because random access is slow.

C Merge sort requires converting the linked list to an array first.

D Merge sort can be implemented efficiently on linked lists without extra space by changing pointers.

💡 Hint

Think about how merging works with linked lists compared to arrays.

Merge sort works well on linked lists because merging can be done by rearranging pointers without extra arrays, making it space efficient.

❓ Predict Output

expert

Output of Merge Sort with Duplicate Elements

What is the output of the following Go code after sorting the array [5, 3, 8, 3, 9, 1, 5] using merge sort?

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, 3, 9, 1, 5}
    sorted := mergeSort(arr)
    fmt.Println(sorted)
}

A [1 3 3 5 5 8 9]

B [1 3 5 3 5 8 9]

C [1 3 3 5 8 9]

D [9 8 5 5 3 3 1]

💡 Hint

Check how duplicates are handled and the stability of merge sort.

Merge sort is stable and sorts duplicates in order, resulting in [1 3 3 5 5 8 9].