Merge Sort Algorithm in DSA Go - Build from Scratch

Merge Sort Algorithm

📖 Scenario: You are working on a program that needs to sort a list of numbers efficiently. Merge Sort is a popular sorting method that splits the list into smaller parts, sorts them, and then merges them back together in order.Imagine you have a messy pile of numbered cards, and you want to arrange them from smallest to largest quickly and neatly.

🎯 Goal: Build a Go program that implements the Merge Sort algorithm to sort a list of integers.You will create the initial list, write the merge function, write the merge sort function, and finally print the sorted list.

📋 What You'll Learn

Create a slice of integers called numbers with the exact values: 38, 27, 43, 3, 9, 82, 10

Create a helper function called merge that merges two sorted slices into one sorted slice

Create a recursive function called mergeSort that splits the slice and uses merge to sort

Print the sorted slice after applying mergeSort

💡 Why This Matters

🌍 Real World

Merge Sort is used in many software systems where efficient and stable sorting is needed, such as databases, search engines, and large data processing.

💼 Career

Understanding merge sort helps in technical interviews and improves problem-solving skills for software development roles.

1

Create the initial slice of numbers

Create a slice of integers called numbers with these exact values: 38, 27, 43, 3, 9, 82, 10

DSA Go

# Create the slice called numbers with the given values
# Your code here

Hint

Use numbers := []int{38, 27, 43, 3, 9, 82, 10} to create the slice.

2

Create the merge function

Create a function called merge that takes two sorted slices of integers named left and right and returns a single sorted slice of integers

DSA Go

package main

import "fmt"

func merge(left []int, right []int) []int {
    // Your code here
}

func main() {
    numbers := []int{38, 27, 43, 3, 9, 82, 10}
}

Hint

Use two indexes to compare elements from left and right, append the smaller to result, then append remaining elements.

3

Create the mergeSort function

Create a recursive function called mergeSort that takes a slice of integers named arr and returns a sorted slice of integers. It should split arr into halves, recursively sort each half, and merge them using the merge function

DSA Go

package main

import "fmt"

func merge(left []int, 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++
        }
    }

    for i < len(left) {
        result = append(result, left[i])
        i++
    }

    for j < len(right) {
        result = append(result, right[j])
        j++
    }

    return result
}

func mergeSort(arr []int) []int {
    // Your code here
}

func main() {
    numbers := []int{38, 27, 43, 3, 9, 82, 10}
}

Hint

Split the slice into two halves, recursively call mergeSort on each half, then merge the results.

4

Print the sorted slice

In the main function, call mergeSort with the numbers slice and print the returned sorted slice using fmt.Println

DSA Go

package main

import "fmt"

func merge(left []int, 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++
        }
    }

    for i < len(left) {
        result = append(result, left[i])
        i++
    }

    for j < len(right) {
        result = append(result, right[j])
        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() {
    numbers := []int{38, 27, 43, 3, 9, 82, 10}
    // Your code here
}

Hint

Call mergeSort(numbers) and print the result with fmt.Println.