Golang: Counting Inversions Sorting issue

I have recently started experimenting with Golang. I'm trying to write a program which counts the number of inversions with a given slice, but I have ran into an issue.

I'm trying to sort the slice using code based off MergeSort, but my code does not seem to sort the slice properly. I'm assuming that the final slice has to be sorted for the inversion count to work correctly, but I don't know how to do this. Can I get some help on this issue?

func InversionCount(a []int) int {
if len(a) <= 1 {
return 0
}
mid := len(a) / 2
left := a[:mid]
right := a[mid:]
leftCount := InversionCount(left)
rightCount := InversionCount(right)
res := make([]int, 0, len(right)+len(left)) //temp slice to hold the sorted left side and right side
iCount := mergeCount(left, right, &res)
a = res        //Copies the result back into the original slice
fmt.Println(a) //Why hasn't "a" been sorted?
return iCount + leftCount + rightCount
}
func mergeCount(left, right []int, res *[]int) int {
count := 0
for len(left) > 0 || len(right) > 0 {
if len(left) == 0 {
*res = append(*res, right...)
break
}
if len(right) == 0 {
*res = append(*res, left...)
break
}
if left[0] <= right[0] {
*res = append(*res, left[0])
left = left[1:]
} else { //Inversion has been found
count += 1
*res = append(*res, right[0])
right = right[1:]
}
}
return count
}
func main() {
s := []int{4, 3, 2, 1}
fmt.Print(InversionCount(s))
}

Here is a link to my code: http://play.golang.org/p/QSJyg_qadD

You need to replace the line

count += 1

with

count += len(left)

The point is that at any point in mergeCount where left[0] > right[0], then since left is already sorted, all the remaining things in left are inverted relative to right[0]. If you do this, you get the correct count.

The fact that your sort isn't working is a different problem. If you're interested in fixing that, I'd recommend taking out all the count logic and just trying to fix the sort. If you're still stuck, it probably deserves its own question.

One problem is that InversionCount(arr) doesn't result in arr being sorted, so

a = res        //Copies the result back into the original slice
fmt.Println(a) //Why hasn't "a" been sorted?

this isn't what you're wanting it to be, because earlier when you apply mergeCount to left and right, those subarrays left and right weren't sorted by InversionCount. A simpler example of this:

package main
import "fmt"
func Foo(a []int) {
a = []int{1, 2, 3, 4}
}
func main() {
a := []int{4, 3, 2, 1}
Foo(a)
fmt.Println(a) // [4, 3, 2, 1]
}