Merge Sort

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

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()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

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))
}