package main

import (
	"fmt"
	"reflect"
	"testing"
)

func Merge(left []int, right []int) []int {
	total := len(left) + len(right)
	items := []int{}

	for i := 0; i < total; i++ {
		if len(left) == 0 || len(right) == 0 {
			break
		}
		if left[0] < right[0] {
			items, left = append(items, left[0]), left[1:]
		} else {
			items, right = append(items, right[0]), right[1:]
		}
	}
	for _, item := range left {
		items = append(items, item)
	}
	for _, item := range right {
		items = append(items, item)
	}
	return items
}

func MergeSort(A []int) []int {
	length := len(A)

	if length <= 1 {
		return A
	}

	mid := length / 2
	left := MergeSort(A[0:mid])
	right := MergeSort(A[mid:])
	return Merge(left, right)
}

func TestMergeSort(t *testing.T) {
	table := []struct {
		in  []int
		out []int
	}{
		{
			in:  []int{3},
			out: []int{3},
		},
		{
			in:  []int{3, 41},
			out: []int{3, 41},
		},
		{
			in:  []int{41, 3},
			out: []int{3, 41},
		},
		{
			in:  []int{3, 3},
			out: []int{3, 3},
		},
		{
			in:  []int{3, 41, 9},
			out: []int{3, 9, 41},
		},
		{
			in:  []int{3, 41, 52, 26, 38, 57, 9, 49},
			out: []int{3, 9, 26, 38, 41, 49, 52, 57},
		},
	}

	for _, test := range table {
		t.Run(fmt.Sprintf("Sort %v", test.in), func(t *testing.T) {
			results := MergeSort(test.in)

			if !reflect.DeepEqual(results, test.out) {
				t.Errorf("Expected: %v, Got: %v", test.out, test.in)
			}
		})
	}
}