Overview

Learning algorithms and data structures with reference to Algorithm Encyclopedia.

The implementation is also available at github - bmf-san/road-to-algorithm-master.

Merge Sort

Recursively divide the data sequence until it can no longer be divided (single element), and sort by repeatedly merging the divided data multiple times
Sort based on the divide and conquer method
- Divide a large problem into smaller problems

Time Complexity

Worst-case time complexity
- O(n log n)

Implementation

// cf. https://github.com/TheAlgorithms/Go/blob/master/sorts/merge_sort.go
package main

func merge(a []int, b []int) []int {
	r := make([]int, len(a)+len(b))
	i := 0
	j := 0

	for i < len(a) && j < len(b) {
		if a[i] <= b[j] {
			r[i+j] = a[i]
			i++
		} else {
			r[i+j] = b[j]
			j++
		}
	}

	for i < len(a) {
		r[i+j] = a[i]
		i++
	}

	for j < len(b) {
		r[i+j] = b[j]
		j++
	}

	return r
}

func mergeSort(n []int) []int {
	if len(n) < 2 {
		return n
	}

	var middle = len(n) / 2
	a := mergeSort(n[:middle])
	b := mergeSort(n[middle:])
	return merge(a, b)
}