package mergesort

import (
	"reflect"
	"testing"
)

// MergeSort returns a sorted copy of nums using merge sort.
func MergeSort(nums []int) []int {
	if len(nums) <= 1 {
		return append([]int(nil), nums...)
	}

	mid := len(nums) / 2
	left := MergeSort(nums[:mid])
	right := MergeSort(nums[mid:])

	return merge(left, right)
}

// merge combines two sorted slices into one sorted slice.
func merge(left, right []int) []int {
	result := make([]int, 0, len(left)+len(right))
	i, j := 0, 0

	for i < len(left) && j < len(right) {
		if left[i] <= right[j] {
			result = append(result, left[i])
			i++
		} else {
			result = append(result, right[j])
			j++
		}
	}

	result = append(result, left[i:]...)
	result = append(result, right[j:]...)

	return result
}

func TestMergeSortOrdersNumbers(t *testing.T) {
	input := []int{8, 3, 5, 1, 9, 2}
	want := []int{1, 2, 3, 5, 8, 9}

	if got := MergeSort(input); !reflect.DeepEqual(got, want) {
		t.Fatalf("MergeSort(%v) = %v, want %v", input, got, want)
	}
}

func TestMergeSortHandlesDuplicatesAndNegatives(t *testing.T) {
	input := []int{4, -1, 4, 0, -7, 2}
	want := []int{-7, -1, 0, 2, 4, 4}

	if got := MergeSort(input); !reflect.DeepEqual(got, want) {
		t.Fatalf("MergeSort(%v) = %v, want %v", input, got, want)
	}
}

func TestMergeSortDoesNotMutateInput(t *testing.T) {
	input := []int{3, 1, 2}
	original := append([]int(nil), input...)

	_ = MergeSort(input)

	if !reflect.DeepEqual(input, original) {
		t.Fatalf("MergeSort mutated input: got %v, want %v", input, original)
	}
}