Go Program for Merge Sort with Example and Explanation

A Go program for merge sort uses a recursive mergeSort function that splits the slice, sorts each half, and merges them with a merge helper; for example, func mergeSort(arr []int) []int { ... }.

Examples

Input[3, 1, 4, 1, 5]

Output[1 1 3 4 5]

Input[10, 9, 8, 7]

Output[7 8 9 10]

Input[]

Output[]

How to Think About It

To sort a list using merge sort, first split the list into two halves until each part has one or zero elements. Then, merge these small sorted parts back together by comparing their elements one by one, building a fully sorted list.

Algorithm

1

Check if the list has one or zero elements; if yes, return it as sorted.

2

Split the list into two halves.

3

Recursively apply merge sort on each half.

4

Merge the two sorted halves into one sorted list.

5

Return the merged sorted list.

Code

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{38, 27, 43, 3, 9, 82, 10}
    sorted := mergeSort(arr)
    fmt.Println(sorted)
}

Output

[3 9 10 27 38 43 82]

Dry Run

Let's trace sorting [38, 27, 43, 3, 9, 82, 10] through the merge sort code

1

Split the array

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

2

Sort left half

Split [38, 27, 43] into [38] and [27, 43], then sort each

3

Sort right half

Split [3, 9, 82, 10] into [3, 9] and [82, 10], then sort each

4

Merge sorted halves

Merge sorted left and right halves step by step to get fully sorted array

Step	Array State
Initial	[38 27 43 3 9 82 10]
Split	[38 27 43] and [3 9 82 10]
Sort left	[27 38 43]
Sort right	[3 9 10 82]
Merge	[3 9 10 27 38 43 82]

Why This Works

Step 1: Divide the array

The mergeSort function splits the array into smaller parts until each part has one or zero elements, which are naturally sorted.

Step 2: Sort each half recursively

Each half is sorted by calling mergeSort again, breaking down the problem into smaller pieces.

Step 3: Merge sorted halves

The merge function combines two sorted slices by comparing their elements one by one, building a fully sorted array.

Alternative Approaches

In-place merge sort

go

package main

import "fmt"

func mergeInPlace(arr []int, start, mid, end int) {
    left := append([]int{}, arr[start:mid+1]...)
    right := append([]int{}, arr[mid+1:end+1]...)
    i, j, k := 0, 0, start
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            arr[k] = left[i]
            i++
        } else {
            arr[k] = right[j]
            j++
        }
        k++
    }
    for i < len(left) {
        arr[k] = left[i]
        i++
        k++
    }
    for j < len(right) {
        arr[k] = right[j]
        j++
        k++
    }
}

func mergeSortInPlace(arr []int, start, end int) {
    if start >= end {
        return
    }
    mid := (start + end) / 2
    mergeSortInPlace(arr, start, mid)
    mergeSortInPlace(arr, mid+1, end)
    mergeInPlace(arr, start, mid, end)
}

func main() {
    arr := []int{38, 27, 43, 3, 9, 82, 10}
    mergeSortInPlace(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

This version sorts the array in place without creating new slices, saving memory but with more complex code.

Iterative bottom-up merge sort

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 mergeSortIterative(arr []int) []int {
    n := len(arr)
    width := 1
    for width < n {
        for i := 0; i < n; i += 2 * width {
            left := arr[i:min(i+width, n)]
            right := arr[min(i+width, n):min(i+2*width, n)]
            merged := merge(left, right)
            copy(arr[i:], merged)
        }
        width *= 2
    }
    return arr
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

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

This iterative approach avoids recursion by merging pairs of subarrays of increasing size.

Complexity: O(n log n) time, O(n) space

Time Complexity

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

Space Complexity

It requires extra space to hold temporary slices during merging, so space complexity is O(n). In-place variants can reduce this.

Which Approach is Fastest?

Recursive merge sort is simple and fast for most cases; iterative and in-place versions save memory but add complexity.

Approach	Time	Space	Best For
Recursive merge sort	O(n log n)	O(n)	Simplicity and clarity
In-place merge sort	O(n log n)	O(1) or O(n)	Memory-limited environments
Iterative merge sort	O(n log n)	O(n)	Avoiding recursion overhead