I'm trying to write a program that counts inversions within an array, but my array is not being sorted properly due to reference issues and thus messes up my count even though I thought slices were passed by reference in Golang.
Here is my code:
package main
import (
"fmt"
)
func InversionCount(a []int) int {
if len(a) <= 1 {
return 0
}
mid := len(a) / 2
left := a[:mid]
right := a[mid:]
leftCount := InversionCount(left) //not being sorted properly due to reference issues
rightCount := InversionCount(right) //not being sorted properly due to reference issues
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 //assigns the original slice with the temp slice values
fmt.Println(a) //a in the end is not sorted properly for most cases
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 += len(left)
*res = append(*res, right[0])
right = right[1:]
}
}
return count
}
func main() {
test := []int{4,2,3,1,5}
fmt.Print(InversionCount(test))
}
What would be the best possible way to solve this problem? I have tried to do something similar to what I did to the res
array by forcing the mergeCount
function to take in a reference of the array, but it seems very messy and it will give me errors.