# Merge Sort in Golang with Examples

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

The post Merge Sort in Golang with Examples first appeared on Qvault.

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 the input slice into two (equal) halves
• Recursively sort the two halves
• Merge the two halves to form a sorted array

Sorry to interrupt! I just wanted to mention that you should check out my new free Go course. It’s designed to teach you all the fundamentals of my favorite coding language.

Learn Golang Now

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}`
`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]}`
• 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 which means that values with duplicate keys in the original list will be in the same order in the sorted list.
• 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.

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.

Thanks for reading, now take a course!

Interested in a high-paying job in tech? Land interviews and pass them with flying colors after taking my hands-on coding courses.

Start coding now

Follow and hit me up on Twitter @q_vault if you have any questions or comments. If I’ve made a mistake in the article be sure to let me know so I can get it corrected!

Subscribe to my newsletter for more coding articles delivered straight to your inbox.

I love Go and Rust, and I like JavaScript and Python. I’m indiehacking on http://qvault.io when my daughter isn’t crying.

We publish several new computer science and coding articles every week. Our articles cover many different programming topics including but certainly not limited to Golang, JavaScript, Vue.js, algorithms, and cryptography. Subscribe for free updates in your inbox.