Merge Sort in Golang

Merge Sort is a famous divide-and-conquer algorithm used for sorting arrays. It works by splitting the array into smaller subarrays, sorting each subarray, and then merging them back together. It was invented by John von Neumann in 1945 and is efficient with a time complexity of O(n log n), making it much faster than simpler algorithms like Bubble Sort and Selection Sort for large datasets.

• Time complexity of O(log n)
• Space complexity of O(n)

Please consider diving into "merge_sort.go" file for more explanation with examples and vizualization!

Glance of the algorithm

Let's see how the algorithm looks:

func MergeSort(array []int) []int {
	if len(array) <= 1 {
		return array
	}

	middle := len(array) / 2
	left := MergeSort(array[:middle])
	right := MergeSort(array[middle:])

	return MergeHalves(left, right)
}

func MergeHalves(left []int, right []int) []int {
	sortedArray := make([]int, len(left)+len(right))
	x := 0
	y := 0

	for k := 0; k < len(sortedArray); k++ {
		switch {
		case x >= len(left):
			sortedArray[k] = right[y]
			y++

		case y >= len(right):
			sortedArray[k] = left[x]
			x++

		case left[x] < right[y]:
			sortedArray[k] = left[x]
			x++

		default:
			sortedArray[k] = right[y]
			y++
		}
	}

	return sortedArray
}

Merge Sort follows three main steps:

1. Divide: The array is split into two halves recursively until each subarray has only one element (which is trivially sorted).

2. Conquer: The sorted subarrays are merged back together in the correct order.

3. Combine: After repeatedly merging all the subarrays, you end up with a fully sorted array.

License

MIT