merge.go

package main

import "fmt"

func mergeSort(arr []int) []int {
	l := len(arr)
	if l <= 1 {
		return arr
	}
	mid := l / 2
	return merge2(mergeSort(arr[:mid]), mergeSort(arr[mid:]))
}

func merge(a1, a2 []int) (s []int) {
	l1, l2 := len(a1), len(a2)

	for i := 0; i < l1+l2; i++ {
		if a1[0] < a2[0] {
			s = append(s, a1[0])
			a1 = a1[1:]
		} else {
			s = append(s, a2[0])
			a2 = a2[1:]
		}

		if len(a1) == 0 {
			s = append(s, a2...)
			break
		}
		if len(a2) == 0 {
			s = append(s, a1...)
			break
		}
	}
	return
}

func merge2(a1, a2 []int) (s []int) {
	l1, l2 := 0, 0

	for l1 < len(a1) && l2 < len(a2) {
		if a1[l1] <= a2[l2] {
			s = append(s, a1[l1])
			l1++
		} else {
			s = append(s, a2[l2])
			l2++
		}
	}
	s = append(s, a1[l1:]...)
	s = append(s, a2[l2:]...)
	return
}

func main() {
	arr := []int{5, 8, 2, 7, 0, 1, 9, 3, 2, 3, 3}
	sortedArr := mergeSort(arr)
	fmt.Println("merged")
	fmt.Println(sortedArr)
}