## DEV Community is a community of 733,030 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Lane Wagner for Qvault

Posted on • Originally published at qvault.io on

# Merge Sort in Golang with Examples 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

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

### Conquer

• Merge the two halves to form a sorted array ## 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)
}
<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.

``````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

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

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