题解 | #数组中的逆序对#

func InversePairs( data []int ) int {
    // write code here
    _ = mergeSort(data)
    return count % 1000000007
}

var count int
func mergeSort(data []int) []int { // 归并排序 
    if len(data) < 2 {
        return data
    }
    mid := len(data) / 2
    l := mergeSort(data[:mid])
    r := mergeSort(data[mid:])
    return mergeCount(l, r)
}
func mergeCount(l, r []int) (tmp []int) {
    var (
        i, j = 0, 0
        l1, l2 = len(l), len(r)
    )
    
    for i < l1 && j < l2 {
        if l[i] <= r[j] {
            tmp = append(tmp, l[i])
            i++
        } else {
            count += l1-i // 利用局部有序性 如{4,5,6} 与 {1,2}，对于元素1则有3个逆序对
            tmp = append(tmp, r[j])
            j++
        }
    }
    tmp = append(tmp, l[i:]...)
    tmp = append(tmp, r[j:]...)
    return tmp
}