排序算法（2）：归并排序

 归并排序：归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(n log n)。

 用归并排序对n个元素的数组进行排序时，当n为2的幂时，元素比较次数在（n log n）/2到n log n - n +1之间，元素被赋值次数为2n log n。时间复杂度O（n log 2n），速度仅次于快排，比较稳定。

 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

 归并排序的核心思想是将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。

merge2.png

合并相邻有序子序列

 再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

merge3.png

代码实现：

package sort

func MergeSort(array []int, left, right int, temp []int) {
    if left < right {
        mid := (left + right) / 2
        MergeSort(array, left, mid, temp)
        MergeSort(array, mid+1, right, temp)
        Merge(array, left, mid, right, temp)
    }
}

func Merge(array []int, left, mid, right int, temp []int) []int {
    leftStart := left
    rightStart := mid + 1
    i := 0
    for {
        if leftStart >= mid || rightStart >= right {
            break
        }
        if array[leftStart] <= array[rightStart] {
            temp[i] = array[leftStart]
            leftStart++
        } else {
            temp[i] = array[rightStart]
            rightStart++
        }
        i++

    }

    for {
        if leftStart < mid {
            temp[i] = array[leftStart]
        }
        leftStart++
        i++
    }

    for {
        if rightStart < right {
            temp[i] = array[rightStart]
        }
        rightStart++
        i++
    }

    return temp
}