归并算法

我们这里不讲归并函数的基础，如果你暂时还不知道归并函数的话，可以看这篇文章理解。

自顶向下

归并算法的图文讲解

不过值得注意的是，这里面的算法有些问题，至少我的GO语言，没有能够重复结果。

我贴一下我的 merge算法

//合并 [left...mid]  [mid+1...right]
func mergeArray(arr []int, left int,mid int, right int,temp []int)  {
    i:=left //左边界
    j:=mid+1//右边界


    for i:=left;i<=right ;i++  {
        temp[i] =arr[i]   //把当前范围对于的数字拷贝进去
    }

    for k := left; k <= right; k++ {
        if i > mid { //当我的左边界超出我的右边界范围
            arr[k]=temp[j]
            j++
        }else if j>right{ //当我的右边界超出我的最大边界
            arr[k] = temp[i]
            i++
        }else if temp[i]<temp[j]{
            arr[k] = temp[i]
            i++
        }else {
            arr[k]=temp[j]
            j++
        }
    }
}

而且这里讲的是，归并当中的自顶向下排序。并没有自底向上的做法。我在这里给大家分析一下

自底向上

和上面的自顶向下相反，我们自底向上的思路是这样的

func mergeSortBTU(arr []int, n int,temp []int) {
    for sz := 1; sz<=n ;sz+=sz  {
        for i := 0; i+sz <=n; i += sz + sz {
                mergeArray(arr, i ,i+sz-1,min(i+sz+sz-1,n),temp)
        }
    }
}