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]