package mergesort

import (
	"reflect"
	"testing"
)

// MergeSort returns a sorted copy of values without modifying the input.
func MergeSort(values []int) []int {
	if len(values) <= 1 {
		return append([]int(nil), values...)
	}

	middle := len(values) / 2
	left := MergeSort(values[:middle])
	right := MergeSort(values[middle:])
	return merge(left, right)
}

// merge combines two sorted slices.
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 TestMergeSort(t *testing.T) {
	input := []int{5, 2, 8, 1, 3, 2}
	want := []int{1, 2, 2, 3, 5, 8}

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

func TestMergeSortEdgeCases(t *testing.T) {
	tests := []struct {
		name  string
		input []int
		want  []int
	}{
		{"empty", []int{}, []int{}},
		{"single", []int{7}, []int{7}},
		{"negatives", []int{-1, -5, 3, 0}, []int{-5, -1, 0, 3}},
	}

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