Merge sort in Go

Merge sort is a popular sorting algorithm, renowned for its efficiency and ability to handle large datasets which uses a divide-and-conquer strategy for sorting. This algorithm divides the input array into two halves, sorts each half recursively, and then merges them together to produce a sorted array. We'll demonstrate how to implement it using the Go programming language.

Approach

Merge sort follows a divide-and-conquer strategy, breaking down the sorting task into smaller subproblems. Here's a high-level overview of the Merge sort algorithm:

Divide: The unsorted array or slice is recursively divided into smaller subarrays until each subarray contains only one element.
Conquer: Individual elements and subarrays are treated as sorted.
Merge: Sorted subarrays are merged to create larger sorted subarrays until the entire array or slice is sorted.

The important step of merge sort lies in the merging step, where sorted subarrays are combined to form larger sorted arrays. This approach ensures stability (equal elements maintain their original order) and guarantees a time complexity of $\text{O(n log n)}$ for average, best, and worst-case scenarios. Moreover, it has a space complexity of $\text{O(n)}$ due to the temporary storage required for merging subarrays during its divide and conquer process.

package main
import (
	"fmt"
)
func mergeSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}
	mid := len(arr) / 2
	left := mergeSort(arr[:mid])
	right := mergeSort(arr[mid:])
	return merge(left, right)
}
func merge(left, right []int) []int {
	result := make([]int, 0, len(left)+len(right))
	i, j := 0, 0
	for i < len(left) && j < len(right) {
		if left[i] < right[j] {
			result = append(result, left[i])
			i++
		} else {
			result = append(result, right[j])
			j++
		}
	}
	result = append(result, left[i:]...)
	result = append(result, right[j:]...)
	return result
}
func main() {
	arr := []int{12, 11, 13, 5, 6, 7}
	fmt.Println("Original array:", arr)
	sorted := mergeSort(arr)
	fmt.Println("Sorted array:", sorted)
}

Lines 7–17: The mergeSort function recursively divides the input slice into smaller subarrays using the mid-point.
- Lines 8–10: Once the subarrays reach a size of 1 or less, they are returned.
Lines 19–37: The merge function combines two sorted subarrays (left and right) into a single sorted array. It uses two pointers, i and j, to iterate through the subarrays and compares elements to determine their order. We have used the append function to append the items into a new array.
- Lines 33–34: After the loop, any remaining elements in either left or right are appended to the result slice to ensure completeness.
Lines 39–45: The main function demonstrates the usage of Merge Sort by sorting an example array. It prints the original and sorted arrays.

Conclusion

Merge sort demonstrates remarkable efficiency when handling large datasets due to its consistent time complexity across various scenarios. Its divide-and-conquer approach ensures that the dataset is recursively divided into smaller subarrays, allowing for parallel processing and efficient memory utilization.

Free Resources

Merge sort in Go

Approach

Code

Conclusion