// 这里的l为闭区间，r为开区间
func MergeSort(arr []int, l, r int) {
	// 只有单个元素，无须排序直接返回
	if r - l <= 1 {
		return
	}

	// 找出中间点，划分区间对左右两个区间进行递归得排序
	mid := l + (r-l) >> 1
	MergeSort(arr, l, mid)
	MergeSort(arr, mid, r)
	Merge(arr, l, mid, r)
}

// 合并两个有序区间
func Merge(arr []int, l, mid, r int) {
	leftArr := make([]int, mid - l)
	rightArr := make([]int, r - mid)
	copy(leftArr, arr[l:mid])
	copy(rightArr, arr[mid:r])
	// 添加哨兵
	leftArr = append(leftArr, math.MaxInt)
	rightArr = append(rightArr, math.MaxInt)

	i, j := 0, 0
	k := l
	for k < r {
		// 一直取最小的元素，插入到原数组
		if leftArr[i] <= rightArr[j] {
			arr[k] = leftArr[i]
			i++
		} else {
			arr[k] = rightArr[j]
			j++
		}
		k++
	}
}

func main() {
	arr := []int{1,2,34,5,2,9,3,4,6,23,5,7,22,14,75,35} 
	MergeSort(arr, 0, len(arr))
	fmt.Println(arr) // 输出 [1 2 2 3 4 5 5 6 7 9 14 22 23 34 35 75]
}

type Node struct {
	Value int
	Next *Node
}

func MergeSort(head *Node) *Node {
	if head.Next == nil {
		return head
	}

	// 快慢指针，用于确定链表中点
	slow, fast := head, head
	prev := slow
	for fast != nil && fast.Next != nil {
		prev = slow
		slow = slow.Next
		fast = fast.Next.Next
	}

	// 找到右区间后，保存并断链
	right := slow
	prev.Next = nil
	// 左区间为head
	left := head
	left = MergeSort(left)
	right = MergeSort(right)
	return Merge(left, right)
}

// 合并两个链表并返回头节点
func Merge(left *Node, right *Node) *Node {
	dummy := &Node{}
	p := dummy
	for left != nil && right != nil {
		if left.Value <= right.Value {
			p.Next = left
			left = left.Next
		} else {
			p.Next = right
			right = right.Next
		}
		p = p.Next
	}
	if left != nil {
		p.Next = left
	}
	if right != nil {
		p.Next = right
	}
	return dummy.Next
}

func main() {
	arr := []int{1,2,34,5,2,9,3,4,6,23,5,7,22,14,75,35}
	head := &Node{}
	p := head
	for _, v := range arr {
		p.Next = &Node{Value: v}
		p = p.Next
	}
	p = MergeSort(head)

	for p != nil {
		fmt.Printf("%d ", p.Value)
		p = p.Next
	}
	// 输出 [1 2 2 3 4 5 5 6 7 9 14 22 23 34 35 75]
	fmt.Println()
}