golang 归并排序算法
package main
import (
"fmt"
)
var arr = []int{10, 5, 3, 9, 2, 3, 7, 8, 1, 25, 12}
var arrTmp = make([]int, len(arr))
func main() {
fmt.Println(arr)
MergeSort(arr, 0, len(arr)-1)
fmt.Println(arr)
}
// MergeSort MergeSort
func MergeSort(arr []int, low, high int) []int {
if low >= high {
return make([]int, 0)
}
mid := low + (high-low)/2
MergeSort(arr, low, mid)
MergeSort(arr, mid+1, high)
Merge(arr, low, mid, high)
return arr
}
// Merge Merge
func Merge(arr []int, low, mid, high int) {
i, j := low, mid+1
for n := low; n <= high; n++ {
arrTmp[n] = arr[n]
}
for n := low; n <= high; n++ {
if i > mid {
arr[n] = arrTmp[j]
j++
} else if j > high {
arr[n] = arrTmp[i]
i++
} else if arrTmp[i] < arrTmp[j] {
arr[n] = arrTmp[i]
i++
} else {
arr[n] = arrTmp[j]
j++
}
}
}