マージソート

package main

import (
	"fmt"
	"math/rand"

	"algorithm/sorts"
)

func main() {
	nums := 10
	members := make([]int, nums, nums)
	for i := 0; i < nums; i++ {
		members[i] = rand.Intn(100)
	}
	fmt.Println(sorts.Merge(members))
}

package sorts

import (
	"cmp"
)

func Merge[T cmp.Ordered](members []T) []T {
	length := len(members)
	if 1 >= length {
		return members
	}

	mid := length / 2
	sortedLeft := Merge(members[:mid])
	sortedRight := Merge(members[mid:])

	var result []T
	l, r := 0, 0
	// 整列済みのsortedLeft or sortedRightのどちらかを最後までresultに詰める
	for l < len(sortedLeft) && r < len(sortedRight) {
		if sortedLeft[l] < sortedRight[r] {
			result = append(result, sortedLeft[l])
			l++
		} else {
			result = append(result, sortedRight[r])
			r++
		}
	}

	// sortedLeft or sortedRightの余ったソート済みのリストをresultの最後尾に連結する
	result = append(result, sortedLeft[l:]...)
	result = append(result, sortedRight[r:]...)

	return result
}