package mergesort

import (
	"reflect"
	"testing"
)

// MergeSort returns a sorted copy of nums using merge sort.
// The input slice is not modified.
func MergeSort(nums []int) []int {
	if len(nums) <= 1 {
		out := make([]int, len(nums))
		copy(out, nums)
		return out
	}

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

	return merge(left, right)
}

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

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

	out = append(out, left[i:]...)
	out = append(out, right[j:]...)
	return out
}

func TestMergeSort(t *testing.T) {
	tests := []struct {
		name string
		in   []int
		want []int
	}{
		{"empty", []int{}, []int{}},
		{"single", []int{7}, []int{7}},
		{"already sorted", []int{1, 2, 3, 4}, []int{1, 2, 3, 4}},
		{"reverse sorted", []int{5, 4, 3, 2, 1}, []int{1, 2, 3, 4, 5}},
		{"duplicates and negatives", []int{3, -1, 2, 3, 0, -1}, []int{-1, -1, 0, 2, 3, 3}},
	}

	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			got := MergeSort(tt.in)
			if !reflect.DeepEqual(got, tt.want) {
				t.Fatalf("MergeSort(%v) = %v, want %v", tt.in, got, tt.want)
			}
		})
	}
}

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

	_ = MergeSort(in)

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