Merge Sort in Golang with Examples

A learning path to your next coding job

1. Join the Qvault community and share your career goals
3. Complete recommended courses and projects
4. Find your next opportunity with a newly polished resume

Our courses include but are not limited to

• Golang, Python, JavaScript
• Algorithms, data structures, cryptography
• Graphics and functional programming

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.

```.wp-block-code {
border: 0;
}

.wp-block-code > div {
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```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)
}```Code language: Go (go)```

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
}```Code language: Go (go)```

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]
}```Code language: Go (go)```

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.

Trying to find your next programming job?

If you are a self-taught developer having trouble finding your first programming job, we've got your back! We have the learning resources and tight-knit dev community that you need to land the coding job you've been looking for. To get started, create a free account and join our Discord community.

Have questions or feedback?

If we've made a mistake in the article, please let us know so we can get it corrected!