归并排序利用分治思想：

  1. 找区间中点作为分界点
  2. 递归排序；
    • 左半区间和右半区间分别排好序。
  3. 合并左半区间和右半区间。
    • 递归终止条件满足时，才开始拼最终结果。
    • 借助一个辅助数组来暂存部分排好序的区间内的数，归并完后赋值回原数组。
var tmp []int
func ms(nums []int, l, r int) {
    if l == r {
        return
    }
    
    mid := (l+r)/2
    ms(nums, l, mid)
    ms(nums, mid+1, r)
    
    pl, pr := l, mid+1
    c := l
    for pl <= mid && pr <= r {
        if nums[pl] < nums[pr] {
            tmp[c] = nums[pl]
            pl++
        } else {
            tmp[c] = nums[pr]
            pr++
        }
        c++
    }
    for pl <= mid {
        tmp[c] = nums[pl]
        pl++
        c++
    }
    for pr <= r {
        tmp[c] = nums[pr]
        pr++
        c++
    }
    for i := l; i <= r; i++ {
        nums[i] = tmp[i]
    }
}
func mergeSort(nums []int) {
    ms(nums, 0, len(nums)-1)
}
func main() {
    var n int
    fmt.Scanf("%d", &n)
    nums := make([]int, n)
    tmp = make([]int, n)
    for i := range nums {
        fmt.Scanf("%d", &nums[i])
    }
    
    mergeSort(nums)
    for _, n := range nums {
        fmt.Printf("%d ", n)
    }
    fmt.Println()
}

逆序对：后面的数比前面的大，这样的一对数就构成一对逆序对。

package main

import "fmt"

var tmp []int

func ms(nums []int, l, r int) int {
    if l == r {
        return 0
    }
    
    mid := (l+r)/2
    rpn := ms(nums, l, mid) + ms(nums, mid+1, r)
    
    pl, pr := l, mid+1
    c := l
    for pl <= mid && pr <= r {
        if nums[pl] <= nums[pr] {
            tmp[c] = nums[pl]
            pl++
        } else {
            // [pl, mid] 范围内的数相对于 nums[pr] 都是逆序的
            tmp[c] = nums[pr]
            pr++
            rpn += mid-pl+1
        }
        c++
    }
    for pl <= mid {
        tmp[c] = nums[pl]
        pl++
        c++
    }
    for pr <= r {
        tmp[c] = nums[pr]
        pr++
        c++
    }
    for i := l; i <= r; i++ {
        nums[i] = tmp[i]
    }
    
    return rpn
}
func reversedPairs(nums []int) int {
    return ms(nums, 0, len(nums)-1)
}
func main() {
    var n int
    fmt.Scanf("%d", &n)
    nums := make([]int, n)
    tmp = make([]int, n)
    for i := range nums {
        fmt.Scanf("%d", &nums[i])
    }
    
    fmt.Println(reversedPairs(nums))
}

References