排序算法-归并排序

归并排序是一种效率比较高的排序算法，但是它额外需要一个和需要排序的数组同样大小的空间。但是在时间和空间进行取舍，我们一般会选择时间优先。
归并排序的思想是将一个数组分为两半，然后每个再分为两半，依次继续分，直到每个元素为一个单独的数组，然后可以认为它们每个都是有序的。接下来就是相邻的两个小数组合并为一个较大有序数组，合并完成之后，成为每个具有两个元素的有序小数组，再进行合并，最后整个序列变为一个有序序列。
这里的难点在于如何将两个有序的小数组合并为一个有序的较大数组。这里采用分治的思想来解决这个问题。

func merger(arr1 []int, arr2 []int) {
    // 存放排序完成的数组
    arr3 := make([]int, len(arr1)+len(arr2))
    for i, j, k := 0, 0, 0; k < len(arr3); k++ {
        // 如果i越界则说明arr1已经全部进入arr3
        // j越界说明arr2全部进入arr3
        // 剩下的操作只需要把剩余一个数组的剩余元素放入arr3
        if i > len(arr1)-1 {
            arr3[k] = arr2[j]
            j++
        } else if j > len(arr2)-1 {
            arr3[k] = arr1[i]
            i++
        } else if arr1[i] < arr2[j] {
            arr3[k] = arr1[i]
            i++
        } else {
            arr3[k] = arr2[j]
            j++
        }
    }
    // 显示结果
    for _, e := range arr3 {
        fmt.Println(e)
    }
}

上面我们完成了将两个有序数组合并为一个有序数组，那么归并排序就显而易见了

func mergeSort(arr []int, l int, r int) {
    if l >= r {
        return
    }
    mid := int((l + r) / 2)
    mergeSort(arr, l, mid)
    mergeSort(arr, mid+1, r)
    merge(arr, l, mid, r)
}

func merge(arr []int, l int, mid int, r int) {
    aux := make([]int, r-l+1)
    copy(aux, arr[l:r+1])
    i, j, k := l, mid+1, l
    for k <= r {
        if i > mid {
            arr[k] = aux[j-l]
            j++
        } else if j > r {
            arr[k] = aux[i-l]
            i++
        } else if aux[i-l] < aux[j-l] {
            arr[k] = aux[i-l]
            i++
        } else {
            arr[k] = aux[j-l]
            j++
        }
        k++
    }
}