Prepare for a backend job by mastering computer science fundamentals

Merge Sort in Golang with Examples

By Lane Wagner on Jun 10, 2021

Merge sort is a recursive sorting algorithm and, luckily for us, it’s quite a bit faster than bubble sort. Merge sort is a divide and conquer algorithm.

Divide

Conquer

Full example of the merge sort algorithm

Merge sort actually has two functions involved, the recursive mergeSort function, and the merge function.

Let’s write the mergeSort() function first. It’s a recursive function, which means it calls itself, and in this case, it actually calls itself twice. The point of the mergeSort function is to split the array into two roughly equal parts, call itself on those parts, then call merge() to fit those halves back together.

func mergeSort(items []int) []int {
    if len(items) < 2 {
        return items
    }
    first := mergeSort(items[:len(items)/2])
    second := mergeSort(items[len(items)/2:])
    return merge(first, second)
}

The merge() function is used for merging two sorted lists back into a single sorted list, its where the “magic” really happens. At the lowest level of recursion, the two “sorted” lists will each have a length of 1. Those single element lists will be merged into a sorted list of length two, and we can build of from there.

func merge(a []int, b []int) []int {
    final := []int{}
    i := 0
    j := 0
    for i < len(a) && j < len(b) {
        if a[i] < b[j] {
            final = append(final, a[i])
            i++
        } else {
            final = append(final, b[j])
            j++
        }
    }
    for ; i < len(a); i++ {
        final = append(final, a[i])
    }
    for ; j < len(b); j++ {
        final = append(final, b[j])
    }
    return final
}

A simple path to your career in backend development

The pace of Boot.dev's JavaScript, Python and Go courses has been perfect for me. The diverse community in Discord is a blast, and other members are quick to help out with detailed answers and explanations.

- Daniel Gerep from Cassia, Brasil

Using the algorithm in code

func main() {
    unsorted := []int{10, 6, 2, 1, 5, 8, 3, 4, 7, 9}
    sorted := mergeSort(unsortedInput)

    // sorted = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
}

Why use merge sort?

Pros

Cons

If you need a sorting algorithm to use in a production system, I recommend not reinventing the wheel and using the built-in sort.Sort method.

Merge sort Big-O complexity

Merge sort has a complexity of O(n*log(n)). Don’t be fooled because there aren’t an explicit number of for-loops to count in the code. In merge sort’s case, the number of recursive function calls is important.

Become a backend engineer by building real projects

Related Reading