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

func InversePairs( data []int ) int {
    // write code here
    tmp := make([]int, len(data))
    count := 0
    mergeSort(data, tmp, 0, len(data) - 1, &count)
    return count 
}

func mergeSort(data, tmp []int, start, end int, count *int) {
    if start >= end {
        return  
    }
    
    mid := start + (end - start) >> 1 
    
    mergeSort(data, tmp, start, mid, count)
    mergeSort(data, tmp, mid+1, end, count)
    merge(data, tmp, start, mid, end, count)
    
    return 
    
}

func merge(data, tmp []int, start, mid, end int, count *int) {
    if start >= end {
        return 
    }
    
    i := start 
    j := mid + 1 
    k := start 
    for i <= mid && j <= end {
        if data[i] <= data[j] { 
            tmp[k] = data[i]
            i++
        } else {
            *count = *count + (mid - i + 1) 
            *count = *count % 1000000007
            tmp[k] = data[j]
            j++
        }
        k++ 
    }
    
    for i <= mid {
        tmp[k] = data[i]
        i++
        k++ 
    }
    
    for j <= end {
        tmp[k] = data[j]
        j++ 
        k++ 
    }
    
    for i = start; i <= end; i++ {
        data[i] = tmp[i]
    }
    
    return 
}