merge_sort.go

package main
import(
	"fmt"
)
func main() {
	// TEST
	arr := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84,1,100,5,23}
	fmt.Println(merge_sort(arr))
}

func merge_sort(array []int) []int{
	if len(array) < 2{
		return array //Consider it sorted
	}
	array_size := len(array)
	
	middle := array_size / 2
	left := array[0:middle]
	right := array[middle:array_size]

	left = merge_sort(left)
	right = merge_sort(right)

	if left[(len(left)-1)] <= right[0]{
		return append(left,right...)
	}
	return merge(left,right)
}

func merge(left,right []int) []int{
	result := make([]int,0)
	var x int
	for len(left) > 0 && len(right) > 0{
		if(left[0] <= right[0]){
			// shift
			x = left[0]
			left = left[1:] 
		}else{
			 // shift
			x = right[0]
			right = right[1:]
		}
		result = append(result,x) // push
	}
	if len(left) > 0{
		result = append(result,left...) //Append the rest of left
	}
	if len(right) > 0{
		result = append(result,right...) //Append the rest of left
	}
	return result
}