# Golang program for implementation of Merge Sort

Merge Sort is a Divide and Conquer algorithm. Meaning, the algorithm splits an input into various pieces, sorts them and then merges them back together. It divides input slice in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves.

### Example

```
``````
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
slice := generateSlice(20)
fmt.Println("\n--- Unsorted --- \n\n", slice)
fmt.Println("\n--- Sorted ---\n\n", mergeSort(slice), "\n")
}
// Generates a slice of size, size filled with random numbers
func generateSlice(size int) []int {
slice := make([]int, size, size)
rand.Seed(time.Now().UnixNano())
for i := 0; i < size; i++ {
slice[i] = rand.Intn(999) - rand.Intn(999)
}
return slice
}
func mergeSort(items []int) []int {
var num = len(items)
if num == 1 {
return items
}
middle := int(num / 2)
var (
left = make([]int, middle)
right = make([]int, num-middle)
)
for i := 0; i < num; i++ {
if i < middle {
left[i] = items[i]
} else {
right[i-middle] = items[i]
}
}
return merge(mergeSort(left), mergeSort(right))
}
func merge(left, right []int) (result []int) {
result = make([]int, len(left) + len(right))
i := 0
for len(left) > 0 && len(right) > 0 {
if left[0] < right[0] {
result[i] = left[0]
left = left[1:]
} else {
result[i] = right[0]
right = right[1:]
}
i++
}
for j := 0; j < len(left); j++ {
result[i] = left[j]
i++
}
for j := 0; j < len(right); j++ {
result[i] = right[j]
i++
}
return
}
```

### Output

```
``````
--- Unsorted ---
[-356 328 705 -199 -373 108 -377 -362 128 98 1 -9 -500 -607 387 12 210 -600 -351 432]
--- Sorted ---
[-607 -600 -500 -377 -373 -362 -356 -351 -199 -9 1 12 98 108 128 210 328 387 432 705]
```

##### Most Helpful This Week

Golang program for implementation of Comb Sort
Golang program for implementation LIFO Stack and FIFO Queue
Golang program for implementation of Floyd–Warshall Algorithm
Golang program for implementation of Rabin-Karp
Golang program for drawing a Cuboid
Golang program for implementation of Quick Sort
Golang program for implementation of Longest Common Sub-sequence
Golang program for implementation of Linked List
Golang program for implementation of Bubble Sort
Golang program for implementation of Knuth–Morris–Pratt (KMP) Algorithm