Hi there! Today’s post is not from HackerRank. This was an assignment that I
solved for the *Algorithms: Design and Analysis, Part 1* course from Coursera.
The goal is to implement an algorithm presented in the videos. It was explained
in high level and not considering edge cases. I first tried to do it in `C++`

but it was taking me more time than I wanted to spend and then I switched to
`Go`

and it was blazing fast to code. What really helped me to solve it fast was
the idea of a `slice`

in `Go`

. Slices can be partitioned easily. For instance

`P := a[:m]`

,`P`

is a slice with all elements up to index`m`

exclusively from`a`

`Q := a[m:]`

,`Q`

is a slice with all elements from index`m`

inclusively to the end of`a`

In `C++`

, the above operations would require me more lines of code. I would need
to check the end of my vector `a`

, declare two new `vector<int>`

`P`

and `Q`

and
then add half of the elements in each newly allocated vector using a `for`

loop.

The assignment required to me to count the inversions of a given unordered list. Below is an example.

```
input = [6, 5, 4, 3, 2, 1]
# list after sorting
output = [1, 2, 3, 4, 5, 6]
# number of inversions found
inversions = 15
```

The number of inversions is maximum when the list is in reverse order like the example above. When we look at 6, we see there are five elements out of order after it. Then looking at 5 we see four elements out of order after it. In the end, we count 5+4+3+2+1 = 15 inversions for the example. The formula for the maximum number of inversions in a list of integers of size $n$ is $$f(n) = \left(\begin{array}{c}n\ 2\end{array}\right) = \frac{n(n-1)}{2}.$$

My solution is presented below and it requires the first input to be `N`

, the
number of integers that will be fed to the program, and then the `N`

integers
need to be separated by `\n`

. I just did that because the input they gave me was
a text file with all numbers separated by `\n`

.

```
package main
import (
"fmt"
"math"
)
// result is the merged list and the
// number of inversions
func merge(a []int, b []int, n0 int) ([]int, int) {
n := 0 // number of inversions
m := len(a) + len(b)
result := make([]int, m)
i := 0
j := 0
// print(b)
for k := 0; k < m; k++ {
// --- edge cases -----
if i == len(a) {
result[k] = b[j]
j++
continue
}
if j == len(b) {
result[k] = a[i]
i++
continue
}
// -- general cases --
if a[i] < b[j] {
result[k] = a[i]
i++
} else {
result[k] = b[j]
j++
// add number of inversions
// for current merging
n += len(a) - i
}
}
return result, n + n0
}
func merge_sort(a []int) ([]int, int) {
n := 0
if len(a) > 1 {
// divide and call merge sort
m := int(math.Ceil(float64(len(a)) / 2.0))
P := a[:m]
Q := a[m:]
result1, n1 := merge_sort(P)
result2, n2 := merge_sort(Q)
return merge(result1, result2, n1+n2)
}
return a, n
}
func main() {
// Input file has N
// in the first line
// indicating how many
// lines the file has
N := 0
fmt.Scanf("%d\n", &N)
// allocate memory
X := make([]int, N)
for i := 0; i < N; i++ {
fmt.Scanf("%d\n", &X[i])
}
// Ignore sorted list,
// if needed just change _
// by a name
_, n := merge_sort(X)
fmt.Printf("#Inversions: %d\n", n)
}
```

Running

```
$ go build merge_sort.go
$ ./merge_sort < IntegerArray.txt
#Inversions: 2407905288
```

The main difficulties I had were the edge cases. They were not presented in class and I was having weird bugs saying I was trying to access an out of bounds element of the slice.

That’s all for this assignment, thanks for reading!