package main

import "fmt"

func main() {
	elements := []int{9, 3, 7, 5, 6, 4, 8, 2}
	result := mergeSort(elements)
	fmt.Println(result)
}

func mergeSort(elements []int) []int {
	if len(elements) < 2 {
		return elements
	}
	mid := len(elements) / 2
	return merge(mergeSort(elements[:mid]), mergeSort(elements[mid:]))
}

func merge(left, right []int) []int {
	size, i, j := len(left)+len(right), 0, 0
	merged := make([]int, size)
	for k := 0; k < len(merged); k++ {
		if i > len(left)-1 && j <= len(right)-1 {
			merged[k] = right[j]
			j++
		} else if i <= len(left)-1 && j > len(right)-1 {
			merged[k] = left[i]
			i++
		} else if left[i] < right[j] {
			merged[k] = left[i]
			i++
		} else {
			merged[k] = right[j]
			j++
		}
	}
	return merged
}