package main

import (
	"fmt"
)

var inputData []int = []int{5, 6, 1, 15, 80, 89, 12, 20, 10, 28}

func mergeSort(array []int) []int {
	if len(array) > 1 {
		fmt.Printf("splitting %x ", array)
		var halfArray int = int(len(array) / 2)
		left := array[:halfArray]
		right := array[halfArray:]
		fmt.Printf("to %x %x, halfArray=%x\n", left, right, halfArray)
		left = mergeSort(left)
		right = mergeSort(right)
		fmt.Printf("merging %x and %x { ", left, right)

		out := make([]int, 0, len(left)+len(right))

		lp, rp := 0, 0

		for lp < len(left) && rp < len(right) {
			fmt.Printf("comparing left[%x]=%x and right[%x]=%x, ", lp, left[lp], rp, right[rp])
			if left[lp] == right[rp] {
				out = append(out, right[rp])
				out = append(out, left[lp])
				lp++
				rp++
			} else if left[lp] > right[rp] {
				out = append(out, right[rp])
				rp++
			} else {
				out = append(out, left[lp])
				lp++
			}
		}

		for lp < len(left) {
			fmt.Printf("%x remaining in left, ", lp)
			out = append(out, left[lp])
			lp++
		}

		for rp < len(right) {
			fmt.Printf("%x remaining in right, ", rp)
			out = append(out, right[rp])
			rp++
		}
		fmt.Printf("} to %x\n", out)
		return out
	} else {
		return array
	}
}

func main() {
	fmt.Printf("sorting %x \n", inputData)
	fmt.Printf("sorted %x\n", mergeSort(inputData))
}