Skip to content

Instantly share code, notes, and snippets.

@RichardKnop
Last active February 24, 2019 19:20
Show Gist options
  • Save RichardKnop/426d0465ed2c822e706d40bb68574587 to your computer and use it in GitHub Desktop.
Save RichardKnop/426d0465ed2c822e706d40bb68574587 to your computer and use it in GitHub Desktop.
Merge Sort
package main
import (
"fmt"
)
func main() {
items := []int{4, 202, 3, 9, 6, 5, 1, 43, 506, 2, 0, 8, 7, 100, 25, 4, 5, 97, 1000, 27}
sortedItems := mergeSort(items)
fmt.Println(sortedItems)
}
func mergeSort(items []int) []int {
var n = len(items)
if n == 1 {
return items
}
middle := int(n / 2)
var (
left = make([]int, middle)
right = make([]int, n-middle)
)
for i := 0; i < n; i++ {
if i < middle {
left[i] = items[i]
} else {
right[i-middle] = items[i]
}
}
return merge(mergeSort(left), mergeSort(right))
}
func merge(left, right []int) (result []int) {
result = make([]int, len(left) + len(right))
i := 0
for len(left) > 0 && len(right) > 0 {
if left[0] < right[0] {
result[i] = left[0]
left = left[1:]
} else {
result[i] = right[0]
right = right[1:]
}
i++
}
// Either left or right may have elements left; consume them.
// (Only one of the following loops will actually be entered.)
for j := 0; j < len(left); j++ {
result[i] = left[j]
i++
}
for j := 0; j < len(right); j++ {
result[i] = right[j]
i++
}
return
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment