算法导论的伪代码：

MERGE 函数是合并两个已经排好序的序列。

下面的输入参数：A是一个数组，p,q和r是数组下标，满足 p<=q<=r。下面的函数假设子数组 A[p…q] 和 A[q+1...r]都是已经拍好序的。这个函数将这两个子数组合并成数组A[p...r] 

下面的函数MERGE-SORT排序子数组A[p...r]中的元素，如果p>=r，则该子元素最有有一个元素，所以是已经排好序的。否则，分解步骤简单的计算一个下标q，将A[p...r]分成两个子数组A[p...q]和A[q+1...r]。

Go语言的实现代码：

package main

import "fmt"

func main(){

    arr01:=[]int{34,45,3,6,76,34,46,809,92,8}

    fmt.Print("排序前")

    fmt.Println(arr01)

    mergeSort(arr01,0,len(arr01)-1)

    fmt.Print("排序后")

    fmt.Println(arr01)

}

fund merge1(arr []int,low,mid,high int){

    leftLen:=mid-low+1

    rightLen:=high-mid

    arrLeft:=make([]int,leftLen+1)

    for i:=0;i<leftLen;i++{

        arrLeft[i]=arr[low+i]

    }

    arrLeft[leftLen]=99999//哨兵牌

    arrRight:=make([]int,rightLen+1)

    forj:=0;j<rightLen;j++{

        arrRight[j]=arr[mid+j+1]

    }

    arrRight[rightLen]=99999//哨兵牌

    i,j:=0,0

    for k:=low;k<=high;k++{

        if arrLeft[i]<=arrRight[j]{

            arr[k]=arrLeft[i]

            i++

        }else{

            arr[k]=arrRight[j]

            j++

        }

    }

}

fund mergeSort(arr []int,low,high int){

    if low<high{

        mid:=(low+high)/2

        mergeSort(arr,low,mid)

        mergeSort(arr,mid+1,high)

        merge1(arr,low,mid,high)

    }

}

上面merge代码中，我们可以发现在两个辅助的最后均加入了一个较大的数，即为判断的“哨兵牌”。这样当最后进行循环操作时，每当露出一张“哨兵牌”，程序可以知道该循环已经要结束了。因为“哨兵牌”不可能是两张中较小的，除非另一个数组也出现了“哨兵牌”。如果两个数组均出现了“哨兵牌”，那么就说明了所有的元素都已经放入了数组a中了，而由于数组a的大小限制，循环已经结束了。如果没有设置“哨兵牌”，可能导致一个数组已经没有了元素，而另外一个数组还有一个元素没有放入a中，那么循环中的if判断语句就会失败，直接跳转执行else里面的语句，会导致结果出错。

如果不使用“哨兵牌”，我们同样可以实现merge所做的任务。代码如下：

主要逻辑就是一旦数据 left ，right 所有元素被复制回 arr，就立即停止循环，然后再用一个循环把另外的数组剩余部分复制过去。

可以参考：http://www.cnblogs.com/xjeternity/archive/2011/4/21.html

fund merge2(arr []int,low,mid,highint){

    leftLen:=mid-low+1

    rightLen:=high-mid

    arrLeft:=make([]int,leftLen)

    for i:=0;i<leftLen;i++{

        arrLeft[i]=arr[low+i]

    }

    arrRight:=make([]int,rightLen)

    for j:=0;j<rightLen;j++{

        arrRight[j]=arr[mid+j+1]

    }

    i,j,k:=0,0,low

    for ;k<=high&&i<leftLen&&j<rightLen;k++{

        if arrLeft[i]<=arrRight[j]{

            arr[k]=arrLeft[i]

            i++

        }else{

            arr[k]=arrRight[j]

            j++

        }

    }

    for ;i<leftLen&&k<=high;k++{

        arr[k]=arrLeft[i]

        i++

    }

    for ;j<rightLen&&k<=high;k++{

        arr[k]=arrRight[j]

        j++

    }

}

参考资料：

http://www.cnblogs.com/lxy15329/archive/2013/01/24/sort.html

http://www.cnblogs.com/tonykong/archive/2013/02/05/merge_sort.html

http://www.cnblogs.com/xjeternity/archive/2011/4/21.html