Merge Sort in Golang with Examples
Tags: go
Published: 2021-06-21 13:05:26

---
title: Merge Sort in Golang with Examples
published: true
date: 2021-06-10 12:44:29 UTC
tags: Golang
canonical_url: https://qvault.io/golang/merge-sort-golang/
---

 ![swirl](https://qvault.io/wp-content/uploads/2021/06/swirl.jpg "swirl")

The post [Merge Sort in Golang with Examples](https://qvault.io/golang/merge-sort-golang/) first appeared on [Qvault](https://qvault.io).

Merge sort is a recursive sorting algorithm and, luckily for us, it’s quite a bit faster than [bubble sort](https://qvault.io/golang/bubble-sort-golang/). Merge sort is a [divide and conquer algorithm](https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm).

### Divide

- Divide the input slice into two (equal) halves
- Recursively sort the two halves

### Conquer

- Merge the two halves to form a sorted array

![merge sort gif](https://qvault.io/wp-content/uploads/2021/06/merge_sort_gif.gif "merge sort gif")

## 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.

```go
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)
}
<small id="shcb-language-1"><span>Code language:</span> <span>Go</span> <span>(</span><span>go</span><span>)</span></small>
```

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.

```go
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
}
<small id="shcb-language-2"><span>Code language:</span> <span>Go</span> <span>(</span><span>go</span><span>)</span></small>
```

## Using the algorithm in code

```go
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]
}
<small id="shcb-language-3"><span>Code language:</span> <span>Go</span> <span>(</span><span>go</span><span>)</span></small>
```

## Why use merge sort?

### Pros

- Fast. Merge sort is much faster than bubble sort, being `O(n*log(n))` instead of `O(n^2)`.
- Stable. Merge sort is also a [stable sort](https://en.wikipedia.org/wiki/Category:Stable_sorts) which means that values with duplicate keys in the original list will be in the same order in the sorted list.

### Cons

- Extra memory. Most sorting algorithms can be performed using a single copy of the original array. Merge sort requires an extra array in memory to merge the sorted subarrays.
- Recursive: Merge sort requires many recursive function calls, and function calls can have significant resource overhead.

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](https://qvault.io/golang/sorting-in-go-dont-reinvent-this-wheel/).

## 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.

Ready to take action and get coding?

[<svg aria-hidden="true" role="img" height="1em" width="1em" viewbox="0 0 256 512" xmlns="http://www.w3.org/2000/svg"><path fill="currentColor" d="M224.3 273l-136 136c-9.4 9.4-24.6 9.4-33.9 0l-22.6-22.6c-9.4-9.4-9.4-24.6 0-33.9l96.4-96.4-96.4-96.4c-9.4-9.4-9.4-24.6 0-33.9L54.3 103c9.4-9.4 24.6-9.4 33.9 0l136 136c9.5 9.4 9.5 24.6.1 34z"></path></svg>Try out our coding courses for free](https://app.qvault.io/)

<svg aria-hidden="true" role="img" height="1em" width="1em" viewbox="0 0 256 512" xmlns="http://www.w3.org/2000/svg"><path fill="currentColor" d="M224.3 273l-136 136c-9.4 9.4-24.6 9.4-33.9 0l-22.6-22.6c-9.4-9.4-9.4-24.6 0-33.9l96.4-96.4-96.4-96.4c-9.4-9.4-9.4-24.6 0-33.9L54.3 103c9.4-9.4 24.6-9.4 33.9 0l136 136c9.5 9.4 9.5 24.6.1 34z"></path></svg>[Join our Discord community](https://discord.com/invite/EEkFwbv)

## Have questions or feedback?

Follow and hit me up on Twitter [@q\_vault](https://twitter.com/q_vault) if you have any questions or comments. If I’ve made a mistake in the article be sure to [let me know](https://qvault.io/contact/) so I can get it corrected!