1. merge 函数

merge 负责实现归并的过程，代码如下：

func merge(values, aux []int, left, mid, right int) {
	i, j := left, mid+1
	for k := left; k <= right; k++ {
		if j > right || (i <= mid && values[i] <= values[j]) {
			aux[k] = values[i]
			i++
		} else {
			aux[k] = values[j]
			j++
		}
	}

	for k := left; k <= right; k++ {
		values[k] = aux[k]
	}
}

其中，values 为待排序 slice，aux 为辅助数组，长度与 values 相等。

2. 自顶向下归并排序

func MergeSortTopDown(values []int) {
	n := len(values)
	aux := make([]int, n)

	var mergeSort func(values, aux []int, left, right int)
	mergeSort = func(values, aux []int, left, right int) {
		if left >= right {
			return
		}

		mid := (left + right) >> 1
		mergeSort(values, aux, left, mid)
		mergeSort(values, aux, mid + 1, right)
		merge(values, aux, left, mid, right)
	}

	mergeSort(values, aux, 0, n-1)
}

3. 自底向上归并排序

func MergeSortBottomUp(values []int) {
	n := len(values)
	aux := make([]int, n)

	for sz := 1; sz < n; sz <<= 1 {
		for left := 0; left < n; left += sz << 1 {
			mid, right := left+sz-1, maths.MinInt(left+2*sz-1, n-1)
			merge(values, aux, left, mid, right)
		}
	}
}

其中，maths.MinInt 为自定义的 int 类型比较函数：

func MinInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

4. 自底向上的归并排序可用于实现链表的原地归并排序

例题：LeetCode 148. 排序链表

链表节点定义如下：

type ListNode struct {
    Val  int
    Next *ListNode
}

split 函数用于分段，并返回待归并的两段链表中的第二段：

func split(head *ListNode, n int) *ListNode {
    for i := 1; i < n && head != nil; i++ {
        head = head.Next
    }
    if head == nil {
        return nil
    }
    second := head.Next
    head.Next = nil
    return second
}

merge 函数归并已排序的两段链表，并返回归并后的链表的尾节点：

func merge(left, right *ListNode, head *ListNode) *ListNode {
    cur := head
    for left != nil && right != nil {
        if left.Val <= right.Val {
            cur.Next = left
            left = left.Next
        } else {
            cur.Next = right
            right = right.Next
        }
        cur = cur.Next
    }
    if left != nil {
        cur.Next = left
    } else {
        cur.Next = right
    }

    for cur.Next != nil {
        cur = cur.Next
    }
    return cur
}

排序算法 sortList 实现如下：

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    n := 0
    for cur := head; cur != nil; cur = cur.Next {
        n++
    }

    dummy := &ListNode{Val: -1, Next: head}
    var left, right, tail *ListNode
    for sz := 1; sz < n; sz <<= 1 {
        cur := dummy.Next
        tail = dummy
        for cur != nil {
            left = cur
            right = split(left, sz)
            cur = split(right, sz)
            tail = merge(left, right, tail)
        }
    }

    return dummy.Next
}