The merge sort algorithm is a comparison-based method that was invented by John Von Neumann. Each element in the adjacent list is compared for sorting. The performance of the algorithm is in the order of O(n log n). This algorithm is the best algorithm for sorting a linked list.

Golang Merge Sort Algorithm

The following code snippet demonstrates the merge sort algorithm. The createArray() function takes num int as a parameter and returns an integer, array, that consists of randomized element.

Let's create a file named "merge_sort.go" and add the following source code to it:

package main

// importing fmt and bytes package
import (
	"fmt"
)

// MergeSorter algorithm
func MergeSorter(array []int) []int {

	if len(array) < 2 {
		return array
	}
	var middle int
	middle = (len(array)) / 2
	return JoinArrays(MergeSorter(array[:middle]), MergeSorter(array[middle:]))
}

// Join Arrays method
func JoinArrays(leftArr []int, rightArr []int) []int {

	var num int
	var i int
	var j int
	num, i, j = len(leftArr)+len(rightArr), 0, 0
	var array []int
	array = make([]int, num, num)

	var k int
	for k = 0; k < num; k++ {
		if i > len(leftArr)-1 && j <= len(rightArr)-1 {
			array[k] = rightArr[j]
			j++
		} else if j > len(rightArr)-1 && i <= len(leftArr)-1 {
			array[k] = leftArr[i]
			i++
		} else if leftArr[i] < rightArr[j] {
			array[k] = leftArr[i]
			i++
		} else {
			array[k] = rightArr[j]
			j++
		}
	}
	return array
}

// main method
func main() {

	var elements []int
	elements = []int{11, 4, 18, 6, 19, 21, 71, 13, 15, 2}
	fmt.Println("\n Before Sorting \n\n", elements)
	fmt.Println("\n-After Sorting\n\n", MergeSorter(elements))
}

Run the following command to execute the merge_sort.go file:

G:\GoLang\examples>go run merge_sort.go

 Before Sorting 

 [11 4 18 6 19 21 71 13 15 2]

-After Sorting

 [2 4 6 11 13 15 18 19 21 71]