### Learn back-end development by writing real code

» Merge Sort in Golang With Examples # Merge Sort in Golang with Examples

By Lane Wagner on Jun 10, 2021

Curated backend podcasts, videos and articles. All free.

If you're looking to become a backend developer, or just stay up-to-date with the latest backend technologies and trends, you found the right place. Subscribe below to get a copy of our newsletter, The Boot.dev Beat, each month in your inbox. No spam, no sponsors, totally free.

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

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

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

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