Counting the number of inversions in an array of integers in O(nlogn) time.

inversions.go

package inversions

// SortAndCountInversions uses a divide and conquer approach to determine the number of inversion pairs in an integer array
func SortAndCountInversions(a []int) (sorted []int, inversions int) {
	n := len(a)
	// Base case
	if n == 1 {
		return a, 0
	}

	// Divide
	left := a[:n/2]
	right := a[n/2:]

	// Conquer
	b, x := SortAndCountInversions(left)
	c, y := SortAndCountInversions(right)

	// Merge results
	sorted, z := MergeAndCountInversions(b, c)

	inversions = x + y + z
	return sorted, inversions
}

// MergeAndCountInversions will merge and return the number of inversion pairs using a modified merge sort.
func MergeAndCountInversions(b, c []int) (sorted []int, n int) {
	var i, j int

	size := len(b) + len(c)

	for k := 0; k < size; k++ {
		if b[i] < c[j] {
			sorted = append(sorted, b[i])
			i++
		} else if c[j] <= b[i] {
			n += len(b) - i
			sorted = append(sorted, c[j])
			j++
		}

		if i == len(b) {
			sorted = append(sorted, c[j:]...)
			break
		}

		if j == len(c) {
			sorted = append(sorted, b[i:]...)
			break
		}
	}
	return sorted, n
}