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
Modernizing Legacy Applications: Critical Tips for Organizational Upgrades
How do you create an HTTP server in Go?
Make Your Retirement Luxurious with These 5 Game-Changing Altcoins
How do you set cookies in an HTTP request with an HTTP client in Go?
What is an HTTP client in Go?
How do you handle HTTP client server alerting in Go?
Interface Accepting Address of the Variable in Golang
How to initialize the slice with values using a slice literal?
How do you handle HTTP authentication with an HTTP client in Go?
Comparing Structs with the Different Values Assigned to Data Fields