package kata

func MergeSort(data []int) []int {
	if len(data) <= 1 {
		return data
	}

	mid := len(data) / 2

	return merge(MergeSort(data[:mid]), MergeSort(data[mid:]))
}

func merge(left []int, right []int) []int {
	result := make([]int, 0, len(left) + len(right))
  
	for len(left) > 0 && len(right) > 0 {
		if left[0] < right[0] {
			result = append(result, left[0])
			left = left[1:]
		} else {
			result = append(result, right[0])
			right = right[1:]
		}
	}
  
	
	result = append(result, left...)
	result = append(result, right...)
  
	return result
}