Golang React JS Technology Blog

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
Launches 10 Goroutines and each goroutine adding 10 values to a Channel Example to use various String Functions in Go Language Golang program for drawing a Cuboid Go program to find Name Server (NS) record of a domain Converting Int data type to Float in Go Unveiling the Potential of Quantum Computing in AI: A Game Changer for Industries