Mergesort splits a slice in half over and over until each piece holds one value, then zips the sorted pieces back together on the way up.
The key idea
Merging two sorted lists is easy
- Line the two sorted lists up side by side.
- Look at the first value in each one.
- Move the smaller of the two to the output.
- Repeat until both lists are empty.
Every value moves once, so a merge is a single pass over the two lists.
Strategy
Divide and conquer
Break the list down until every merge is one of those easy ones.
- Divide: split the unsorted slice in half.
- Conquer: keep splitting until each piece holds one value, which is already sorted.
- Combine: merge the sorted pieces back into longer sorted runs.
Purpose
Put a list of values in order, smallest to largest.
Input
An unsorted []int.
Output
A new sorted []int, with the slice you passed in left as it was.
Constraints
- The values have to be comparable with
<=. - Each merge builds a new slice, so sorting a list costs about as much memory again.
- Equal values keep the order they arrived in, so the sort is stable.
How mergesort works
Sorting a pair of values is easy, and joining two sorted runs is easy. Mergesort is those two easy jobs repeated until the whole list is one run.
It takes the same time whatever order the values arrive in, which makes it the safe choice when you cannot say anything about the data.
What mergesort keeps track of
| Name | Type | What it is for |
|---|---|---|
| a | []int | The stretch of values this call is sorting. |
| mid | int | Where the stretch splits into two halves. |
| left | []int | The sorted first half, handed back by a nested call. |
| right | []int | The sorted second half. |
| out | []int | The merged result being built up one value at a time. |
| i | int | Points at the next unused value in left. |
| j | int | Points at the next unused value in right. |
Walk through it
1 Start with a slice
A new sorted slice comes back, and the one you passed in is left alone.
a := []int{38, 27, 43, 3, 9, 82, 10, 1}
sorted := mergeSort(a)2 Stop when a piece is a single value
A piece holding one value, or none, is already in order, so hand it straight back.
if len(a) <= 1 {
return a
}3 Cut the stretch in half
Find the middle, then sort each half by calling the same function on it.
mid := len(a) / 2
left := mergeSort(a[:mid])
right := mergeSort(a[mid:])4 Compare the two front values
Both halves come back sorted, so the smallest value is at the front of one. Take it and step that half forward.
if left[i] <= right[j] {
out = append(out, left[i])
i++
} else {
out = append(out, right[j])
j++
}5 Repeat until one half is empty
Repeat that comparison while both halves still have values waiting.
for i < len(left) && j < len(right) {
// take the smaller front value
}6 Append what is left
One half empties first. Everything left in the other is already sorted, so append it as it is.
out = append(out, left[i:]...)
out = append(out, right[j:]...)The whole program
Put it together and a new sorted slice comes back, smallest to largest.
package main
import "fmt"
// merge joins two already-sorted slices into one sorted slice.
func merge(left, right []int) []int {
out := make([]int, 0, len(left)+len(right))
i, j := 0, 0
for i < len(left) && j < len(right) {
if left[i] <= right[j] {
out = append(out, left[i])
i++
} else {
out = append(out, right[j])
j++
}
}
out = append(out, left[i:]...)
out = append(out, right[j:]...)
return out
}
func mergeSort(a []int) []int {
if len(a) <= 1 {
return a
}
mid := len(a) / 2
left := mergeSort(a[:mid])
right := mergeSort(a[mid:])
return merge(left, right)
}
func main() {
a := []int{38, 27, 43, 3, 9, 82, 10, 1}
fmt.Println(mergeSort(a))
}$ go run main.go
[1 3 9 10 27 38 43 82]