题目描述

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法复杂度

归并排序为稳定排序
平均复杂度为O(nlogn)
最坏复杂度为O(nlogn)
最好复杂度为O(nlogn)

解题思路

• 将一个数组分为两份，分别排序，然后合并两个有序数组。
• 递归对分割的数组再次进行分割，直到数组中只剩一个元素
• 合并的时候按大小进行顺序合并即可

代码实现

func mergeSort(arr []int) []int {
	length := len(arr)
	if length < 2 {
		return arr
	}

	return merge(mergeSort(arr[:length/2]), mergeSort(arr[length/2:]))
}

func merge(arr1, arr2 []int) []int {
	var res []int

	for len(arr1) != 0 && len(arr2) != 0 {
		if arr1[0] <= arr2[0] {
			res = append(res, arr1[0])
			arr1 = arr1[1:]
		} else {
			res = append(res, arr2[0])
			arr2 = arr2[1:]
		}
	}

	if len(arr1) != 0 {
		res = append(res, arr1...)
	}
	if len(arr2) != 0 {
		res = append(res, arr2...)
	}

	return res
}