Golang Merge Sort Algorithm

1. Introduction

Merge Sort is a divide-and-conquer sorting algorithm. It works by recursively splitting the list into two halves until each sub-list consists of a single element, and then merging these smaller lists in sorted order to produce larger, fully sorted lists.

2. Implementation Steps

1. If the list has one or no element, it's already sorted.

2. Divide the list recursively into two halves until each sublist has a single element.

3. Merge the sublists to produce a new, sorted list.

3. Implementation in Golang

package main
import (
	"fmt"
)
// Merge merges two sorted sub-arrays
func Merge(arr []int, l, m, r int) {
	n1 := m - l + 1
	n2 := r - m
	// Create temp arrays
	L := make([]int, n1)
	R := make([]int, n2)
	// Copy data to temp arrays L[] and R[]
	for i := 0; i < n1; i++ {
		L[i] = arr[l+i]
	}
	for j := 0; j < n2; j++ {
		R[j] = arr[m+1+j]
	}
	// Merge the temp arrays back into arr[l..r]
	i, j, k := 0, 0, l
	for i < n1 && j < n2 {
		if L[i] <= R[j] {
			arr[k] = L[i]
			i++
		} else {
			arr[k] = R[j]
			j++
		}
		k++
	}
	// Copy the remaining elements of L[], if there are any
	for i < n1 {
		arr[k] = L[i]
		i++
		k++
	}
	// Copy the remaining elements of R[], if there are any
	for j < n2 {
		arr[k] = R[j]
		j++
		k++
	}
}
// MergeSort sorts the array using merge sort algorithm
func MergeSort(arr []int, l, r int) {
	if l < r {
		// Find the middle point
		m := l + (r-l)/2
		// Sort first and second halves
		MergeSort(arr, l, m)
		MergeSort(arr, m+1, r)
		Merge(arr, l, m, r)
	}
}
func main() {
	data := []int{38, 27, 43, 3, 9, 82, 10}
	fmt.Println("Original array:", data)
	MergeSort(data, 0, len(data)-1)
	fmt.Println("Sorted array:  ", data)
}

Output:

Original array: [38 27 43 3 9 82 10]
Sorted array:   [3 9 10 27 38 43 82]

Explanation:

1. Merge is a helper function that takes in an array and its left, middle, and right indices. It merges two sorted sub-arrays of the given array defined from l to m and m+1 to r.

2. Temporary arrays L and R are used to store the two halves to be merged.

3. The MergeSort function is a recursive function that sorts the input array. It divides the array into two halves, sorts them using MergeSort, and then merges them using the Merge function.

4. In the main function, an array is initialized, displayed in its original state, sorted using MergeSort, and then displayed in its sorted state.

5. Merge Sort is a stable sort with a time complexity of O(n log n) in all three cases (worst, average, and best).

This offers a thorough guide to implementing and understanding the Merge Sort algorithm in Golang.