go-count-inversions

main.go

// Recursive count array inversions O(n.log(n))
package main

import "fmt"

func main() {
	a := []int{2, 1, 4, 3, 6, 5}
	fmt.Println(a, "has", count(a), "inversions.")
}

func count(a []int) int {
	_, c := sortAndCount(a)
	return c
}

func sortAndCount(a []int) ([]int, int) {
	if len(a) <= 1 {
		return a, 0
	}
	n := len(a) / 2

	x, i := sortAndCount(a[:n])
	y, j := sortAndCount(a[n:])
	z, k := mergeAndCount(x, y)
	return z, i + j + k
}

func mergeAndCount(a []int, b []int) ([]int, int) {
	sum := 0
	c := make([]int, 0, len(a)+len(b))
	for {
		if len(a) > 0 && (len(b) == 0 || a[0] <= b[0]) {
			c, a = append(c, a[0]), a[1:]
		} else if len(b) > 0 {
			sum += len(a)
			c, b = append(c, b[0]), b[1:]
		} else {
			break
		}
	}
	return c, sum
}