package main

import "fmt"

func main() {

	arr := []int{4, 1, 3, 2, 5}
	result := MergeSort(arr)
	
	fmt.Println(result)
}

func MergeSort(arr []int) []int {

	if len(arr) == 0 {
		return arr
	}

	return mergeSort(arr)
}

func mergeSort(arr []int) []int {
	
	if len(arr) <= 1 {
		return arr
	}

	mid := len(arr) / 2
	L := arr[:mid]
	R := arr[mid:]

	L = mergeSort(L)
	R = mergeSort(R)
	
	return merge(L, R)
}

func merge(L, R []int) []int {

	i, j, k := 0, 0, 0
	arr := make([]int, len(L)+len(R))
	
	for i < len(L) && j < len(R) {
		if L[i] <= R[j] {
			arr[k] = L[i]
			i += 1
			k += 1
		} else {
			arr[k] = R[j]
			j += 1
			k += 1
		}
	}

	if i < len(L) {
		for i < len(L) {
			arr[k] = L[i]
			i += 1
			k += 1
		}
	}

	if j < len(R) {
		for j < len(R) {
			arr[k] = R[j]
			j += 1
			k += 1
		}
	}

	return arr
}

[1 2 3 4 5]