crossing.go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const (
	datapath = "crossing.txt"
	datasize = 314159
)

func Merge(list, front, end []int) (count int) {
	l_i, f_i, e_i := 0, 0, 0
	for (f_i < len(front)) && (e_i < len(end)) {
		if front[f_i] > end[e_i] {
			list[l_i] = end[e_i]
			e_i++
			count += len(front) - f_i
		} else {
			list[l_i] = front[f_i]
			f_i++
		}
		l_i++
	}

	for ; f_i < len(front); f_i++ {
		list[l_i] = front[f_i]
		l_i++
	}
	for ; e_i < len(end); e_i++ {
		list[l_i] = end[e_i]
		l_i++
	}

	return count
}

func MergeSort(list []int) (count int) {
	length := len(list)
	if length < 2 {
		return count
	}
	front := make([]int, length/2)
	end := make([]int, length-length/2)
	copy(front, list[:length/2])
	copy(end, list[length/2:])

	count += MergeSort(front)
	count += MergeSort(end)
	count += Merge(list, front, end)

	return count
}

func main() {
	path := datapath
	if len(os.Args) > 1 {
		path = os.Args[1]
	}

	f, err := os.Open(path)
	if err != nil {
		panic(err)
	}

	list := make([]int, datasize, datasize)

	i := 0
	scanner := bufio.NewScanner(f)
	for scanner.Scan() {
		n, err := strconv.Atoi(scanner.Text())
		if err != nil {
			panic(err)
		}
		list[i] = n
		i++
	}
	f.Close()

	count := MergeSort(list)
	fmt.Println("count = ", count)
}