In computer science, merge sort (also normally spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. A detailed description and analysis of bottom-up mergesort looked in a report by Goldstine and von Neumann as early as 1948.

Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. divide the unsorted list into N sublists, each containing one component (a list of one component is considered sorted).

```
package main
/*
* Merge sort - http://en.wikipedia.org/wiki/Merge_sort
*/
func Merge(left, right []int) []int {
result := make([]int, 0, len(left) + len(right))
for len(left) > 0 || len(right) > 0 {
if len(left) == 0 {
return append(result, right...)
}
if len(right) == 0 {
return append(result, left...)
}
if left[0] <= right[0] {
result = append(result, left[0])
left = left[1:]
} else {
result = append(result, right[0])
right = right[1:]
}
}
return result
}
func MergeSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
middle := len(arr) / 2
left := MergeSort(arr[:middle])
right := MergeSort(arr[middle:])
return Merge(left, right)
}
```