マージソート
分割統治法（再帰的に細かく問題を分割して解いて、再結集させて全体の答えとする）を使ったアルゴリズム
細かく分割して、それを結集（マージ）するときに、並び替える
O(n * log n)
code:go
package sort
type Order string
const (
ASC Order = "ASC"
DESC Order = "DESC"
)
func MergeSort(arr []int, order Order) {
merged := mergeSort(arr, order)
copy(arr, merged)
}
func mergeSort(arr []int, order Order) []int {
if len(arr) < 2 {
return arr
}
center := len(arr) / 2
left := mergeSort(arr:center, order)
right := mergeSort(arrcenter:, order)
var i, j, k int
merged := make([]int, len(arr))
for i < len(left) && j < len(right) {
if order == DESC {
if lefti <= rightj {
mergedk = rightj
j++
} else {
mergedk = lefti
i++
}
} else {
if lefti >= rightj {
mergedk = rightj
j++
} else {
mergedk = lefti
i++
}
}
k++
}
for i < len(left) {
mergedk = lefti
i++
k++
}
for j < len(right) {
mergedk = rightj
j++
k++
}
return merged
}