归并排序原理

归并排序具体工作原理如下（假设序列共有n个元素）：

将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素

将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素

重复步骤2，直到所有元素排序完毕

示例代码

Go语言 func mergeSort(r []int) []int {    length := len(r)       if length <= 1 {        return r     }       num := length / 2    left := mergeSort(r[:num])       right := mergeSort(r[num:])       return merge(left, right)}func merge(left, right []int) (result []int) {       l, r := 0, 0       for l < len(left) && r < len(right) {        if left[l] < right[r] {                     result = append(result, left[l])                     l++              } else {                     result = append(result, right[r])                     r++              }       }       result = append(result, left[l:]...)       result = append(result, right[r:]...)       return}Java语言 package　algorithmpublic　class　MergeSort　{    //　private　static　long　sum　=　0    /**    　*　<pre>    　*　二路归并    　*　原理：将两个有序表合并和一个有序表    　*　</pre>    　*　    　*　@param　a    　*　@param　s    　*　第一个有序表的起始下标    　*　@param　m    　*　第二个有序表的起始下标    　*　@param　t    　*　第二个有序表的结束小标    　*　    　*/    private　static　void　merge(int[]　a,　int　s,　int　m,　int　t)　{        int[]　tmp　=　new　int[t　-　s　+　1]        int　i　=　s,　j　=　m,　k　=　0        while　(i　<　m　&&　j　<=　t)　{            if　(a[i]　<=　a[j])　{                tmp[k]　=　a[i]                k++                i++            }　else　{                tmp[k]　=　a[j]                j++                k++            }        }        while　(i　<　m)　{            tmp[k]　=　a[i]            i++            k++        }        while　(j　<=　t)　{            tmp[k]　=　a[j]            j++            k++        }        System.arraycopy(tmp,　0,　a,　s,　tmp.length)    }    /**    　*　    　*　@param　a    　*　@param　s    　*　@param　len    　*　每次归并的有序集合的长度    　*/    public　static　void　mergeSort(int[]　a,　int　s,　int　len)　{        int　size　=　a.length        int　mid　=　size　/　(len　<<　1)        int　c　=　size　&　((len　<<　1)　-　1)        //　-------归并到只剩一个有序集合的时候结束算法-------//        if　(mid　==　0)            return        //　------进行一趟归并排序-------//        for　(int　i　=　0　i　<　mid　++i)　{            s　=　i　*　2　*　len            merge(a,　s,　s　+　len,　(len　<<　1)　+　s　-　1)        }        //　-------将剩下的数和倒数一个有序集合归并-------//        if　(c　!=　0)            merge(a,　size　-　c　-　2　*　len,　size　-　c,　size　-　1)        //　-------递归执行下一趟归并排序------//        mergeSort(a,　0,　2　*　len)    }    public　static　void　main(String[]　args)　{        int[]　a　=　new　int[]　{　4,　3,　6,　1,　2,　5　}        mergeSort(a,　0,　1)        for　(int　i　=　0　i　<　a.length　++i)　{            System.out.print(a[i]　+)        }    }}Python语言 def MergeSort(lists):    if len(lists) <= 1:        return lists    num = int( len(lists)/2 )    left = MergeSort(lists[:num])    right = MergeSort(lists[num:])    return Merge(left, right)def Merge(left,right):    r, l=0, 0    result=[]    while l<len(left) and r<len(right):        if left[l] < right[r]:            result.append(left[l])            l += 1        else:            result.append(right[r])            r += 1    result += right[r:]    result+= left[l:]    return resultprint MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45])C语言 #include <stdlib.h>#include <stdio.h>void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex){    int i = startIndex, j=midIndex+1, k = startIndex    while(i!=midIndex+1 && j!=endIndex+1)    {        if(sourceArr[i] >= sourceArr[j])            tempArr[k++] = sourceArr[j++]        else            tempArr[k++] = sourceArr[i++]    }    while(i != midIndex+1)        tempArr[k++] = sourceArr[i++]    while(j != endIndex+1)        tempArr[k++] = sourceArr[j++]    for(i=startIndex i<=endIndex i++)        sourceArr[i] = tempArr[i]}//内部使用递归void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex){    int midIndex    if(startIndex < endIndex)    {        midIndex = (startIndex + endIndex) / 2        MergeSort(sourceArr, tempArr, startIndex, midIndex)        MergeSort(sourceArr, tempArr, midIndex+1, endIndex)        Merge(sourceArr, tempArr, startIndex, midIndex, endIndex)    }}int main(int argc, char * argv[]){    int a[8] = {50, 10, 20, 30, 70, 40, 80, 60}    int i, b[8]    MergeSort(a, b, 0, 7)    for(i=0 i<8 i++)        printf(%d , a[i])    printf(\n)    return 0}PHP语言 //merge函数将指定的两个有序数组(arr1arr2,)合并并且排序//我们可以找到第三个数组,然后依次从两个数组的开始取数据哪个数据小就先取哪个的,然后删除掉刚刚取过///的数据functional_merge($arrA,$arrB){    $arrC = array()    while(count($arrA) && count($arrB)){        //这里不断的判断哪个值小,就将小的值给到arrC,但是到最后肯定要剩下几个值,        //不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值,肯定比arrC里面所有的值都大所以使用        $arrC[] = $arrA['0'] < $arrB['0'] ? array_shift($arrA) : array_shift($arrB)    }    returnarray_merge($arrC, $arrA, $arrB)}//归并排序主程序functional_merge_sort($arr){    $len=count($arr)    if($len <= 1)        return $arr//递归结束条件,到达这步的时候,数组就只剩下一个元素了,也就是分离了数组    $mid = intval($len/2)//取数组中间    $left_arr = array_slice($arr, 0, $mid)//拆分数组0-mid这部分给左边left_arr    $right_arr = array_slice($arr, $mid)//拆分数组mid-末尾这部分给右边right_arr    $left_arr = al_merge_sort($left_arr)//左边拆分完后开始递归合并往上走    $right_arr = al_merge_sort($right_arr)//右边拆分完毕开始递归往上走    $arr=al_merge($left_arr, $right_arr)//合并两个数组,继续递归    return $arr}$arr = array(12, 5, 4, 7, 8, 3, 4, 2, 6, 4, 9)print_r(al_merge_sort($arr))Pascal语言 program　mergesort_1const　maxn=7type　arr=array[1..maxn]　of　integervar　a,b,c:arri:integerprocedure　merge(r:arrl,m,n:integervarr2:arr)var　i,j,k,p:integerbegin　i:=l　j:=m+1　k:=l-1　while　(i<=m)　and　(j<=n)　do　begin　k:=k+1　if　r[i]<=r[j]　then　begin　r2[k]:=r[i]　i:=i+1　end　else　begin　r2[k]:=r[j]　j:=j+1　end　end　if　i<=m　then　for　p:=i　to　m　do　begin　k:=k+1　r2[k]:=r[p]　end　if　j<=n　then　for　p:=j　to　n　do　begin　k:=k+1　r2[k]:=r[p]　endendprocedure　mergesort(var　r,r1:arrs,t:integer)var　k:integerc:arrbegin　if　s=t　then　r1[s]:=r[s]　else　begin　k:=(s+t)div2　mergesort(r,c,s,k)　mergesort(r,c,k+1,t)　merge(c,s,k,t,r1)　endendbegin　write('Enterdata:')　for　i:=1　to　maxn　do　read(a[i])　mergesort(a,b,1,maxn)　for　i:=1　to　maxn　do　write(b[i]:9)　writelnend.//============================================program　mergesort_2const　max=100000var　a,r:array[1..max]　of　long　intn,i:long　intprocedure　msort(s,t:longint)var　m,i,j,k:long　intbegin　if　s=t　then　exit　m:=(s+t)div2　msort(s,m)　msort(m+1,t)　i:=s　j:=m+1　k:=s　while　(i<=m)　and　(j<=t)　do　begin　if　a[i]<a[j]　then　begin　r[k]:=a[i]　inc(i)　inc(k)　end　else　begin　r[k]:=a[j]　inc(j)　inc(k)　end　end　while　i<=m　do　begin　r[k]:=a[i]　inc(i)　inc(k)　end　while　j<=t　do　begin　r[k]:=a[j]　inc(j)　inc(k)　end　for　i:=s　to　t　do　a[i]:=r[i]endbegin　readln(n)　for　i:=1　to　n　do　read(a[i])　msort(1,n)　for　i:=1　to　n　do　writeln(a[i])end.Basic语言 Sub MergeSort(Array() As Integer, First As Integer, Last As Integer)Dim mid As Integer = 0If first<last Then mid = (first+last)\ 2MergeSort(Array, first, mid)MergeSort(Array, mid+1, last)Merge(Array, first, mid, last)End IfEnd Sub/*以下示例代码实现了归并操作。array[]是元素序列，其中从索引p开始到q位置，按照升序排列，同时，从(q+1)到r也已经按照升序排列，merge()函数将把这两个已经排序好的子序列合并成一个排序序列。结果放到array中。*//*** 0 <= p <= q < r, subarray array[p..q] and array[q+1..r] are already sorted.* the merge() function merges the two sub-arrays into one sorted array.*/void Merge(int array[], int p, int q, int r){    int i,k    int begin1,end1,begin2,end2    int* temp = (int*)malloc((r-p+1)*sizeof(int))    begin1 = p    end1   = q    begin2 = q+1    end2   = r    k = 0    while((begin1 <= end1)&&( begin2 <= end2))    {        if(array[begin1] <= array[begin2]){             temp[k] = array[begin1]            begin1++        }        else        {            temp[k] = array[begin2]            begin2++        }        k++    }    while(begin1<=end1 || begin2<=end2)    {        if(begin1<=end1)        {            temp[k++] = array[begin1++]        }        if(begin2<=end2)        {            temp[k++] = array[begin2++]        }        }        for (i = 0 i < =(r - p) i++)            array[p+i] = temp[i]    free(temp)}JavaScript语言

使用递归的代码如下。优点是描述算法过程思路清晰，缺点是使用递归，mergeSort()函数频繁地自我调用。长度为n的数组最终会调用mergeSort()函数 2n-1次，这意味着一个长度超过1500的数组会在Firefox上发生栈溢出错误。可以考虑使用迭代来实现同样的功能。 function　merge(left, right){    var　result=[]    while(left.length>0 && right.length>0){        if(left[0]<right[0]){        /*shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。*/            result.push(left.shift())        }else{            result.push(right.shift())        }    }    return　result.concat(left).concat(right)}function　mergeSort(items){    if(items.length == 1){        return　items}var　middle = Math.floor(items.length/2),    left = items.slice(0, middle),    right = items.slice(middle)    return　merge(mergeSort(left), mergeSort(right))}非递归算法（C++） #include<iostream>#include<ctime>#include<cstring>#include<cstdlib>using namespace std/**将a开头的长为length的数组和b开头长为right的数组合并n为数组长度，用于最后一组*/void　Merge(int*　data,int　a,int　b,int　length,int　n){　int　right　if(b+length-1 >= n-1)　right = n-b　else　right = length　int*　temp = new　int[length+right]　int　i=0, j=0　while(i<=length-1 && j<=right-1){    　if(data[a+i] <= data[b+j]){    　    temp[i+j] = data[a+i]i++      }    　else{        temp[i+j] = data[b+j]        j++      }　}　if(j == right){//a中还有元素，且全都比b中的大,a[i]还未使用　  memcpy(temp + i + j, data + a + i, (length - i) * sizeof(int))　}  else if(i == length){      memcpy(temp + i + j, data + b + j, (right - j)*sizeof(int))  }　memcpy(data+a, temp, (right + length) * sizeof(int))　delete [] temp}void　MergeSort(int*　data, int　n){　int　step = 1　while(step < n){    　for(int　i=0 i<=n-step-1 i+=2*step)    　    Merge(data, i, i+step, step, n)    //将i和i+step这两个有序序列进行合并    //序列长度为step    //当i以后的长度小于或者等于step时，退出    　step*=2//在按某一步长归并序列之后，步长加倍　}}int　main(){　int　n　cin>>n　int*　data = new　int[n]　if(!data)　exit(1)　int　k = n　while(k--){　    cin>>data[n-k-1]　}　clock_t　s = clock()　MergeSort(data, n)　clock_t　e = clock()　k=n　while(k--){　    cout<<data[n-k-1]<<' '　}　cout<<endl　cout<<the algorithm used<<e-s<<miliseconds.<<endl　delete　data　return　0}二路归并

ConstFI='in.txt'FO='out.txt'MaxN=10000TypeTIndex=LongintTDat=Array[0..MaxN]OfTIndexVarN:TIndexDat:TDatTmp:TDatProcedureMerge(L,Mid,R:TIndex)VarP1,P2:TIndexE1,E2:TIndexP:TIndexI:TIndexBeginP1:=LP2:=Mid+1P:=LRepeatIf(Dat[P1]<=Dat[P2])ThenBeginTmp[P]:=Dat[P1]Inc(P1)Inc(P)EndElseBeginTmp[P]:=Dat[P2]Inc(P2)Inc(P)EndUntil(P1=Mid+1)Or(P2=R+1)If(P1=Mid+1)ThenBeginE1:=P2E2:=REndElseBeginE1:=P1E2:=MidEndForI:=E1ToE2DoBeginTmp[P]:=Dat[I]Inc(P)EndEndProcedureSort(L,R:TIndex)VarMid:TIndex=0BeginMid:=(L+R)Shr1If(L<Mid)ThenSort(L,Mid)If(Mid+1<R)ThenSort(Mid+1,R)Merge(L,Mid,R)ForMid:=LToRDoDat[Mid]:=Tmp[Mid]EndProcedureInitVarI:TIndexBeginFillChar(Dat,SizeOf(Dat),0)Readln(N)ForI:=1ToNDoRead(Dat[I])EndProcedureMainBeginSort(1,N)EndProcedureFinalVarI:TIndexBeginForI:=1ToNDoWrite(Dat[I],'')WritelnEndBeginAssign(Input,FI)Assign(Output,FO)Reset(Input)Rewrite(Output)InitMainFinalClose(Input)Close(Output)End.

Delphi归并排序完整源代码例子： //合并子函数procedureTForm1.MergePass(vardatas:arrayofIntegerleft,mid,right:Integer)vartmpArr:arrayofIntegerarrLen:Integeri,k:Integerbegin1,begin2,end1,end2:IntegerbeginarrLen:=right-left+1SetLength(tmpArr,arrLen)begin1:=leftend1:=midbegin2:=mid+1end2:=rightk:=0while((begin1<=end1)and(begin2<=end2))dobeginif(datas[begin1]<datas[begin2])thenbegintmpArr[k]:=datas[begin1]Inc(begin1)endelsebegintmpArr[k]:=datas[begin2]Inc(begin2)endinc(k)endwhile(begin1<=end1)dobegintmpArr[k]:=datas[begin1]Inc(begin1)Inc(k)endwhile(begin2<=end2)dobegintmpArr[k]:=datas[begin2]Inc(begin2)Inc(k)endfori:=0to(right-left)dobegindatas[left+i]:=tmpArr[i]endend//排序主函数，left是数组左下标，0开始。right是数组右下标。procedureTForm1.MergeSort(vardatas:arrayofIntegerleft,right:Integer)varmid:Integeri:Integerbeginmid:=0if(left<right)thenbeginmid:=(right+left)div2showLog('中间索引：'+inttostr(mid))MergeSort(datas,left,mid)MergeSort(datas,mid+1,right)MergePass(datas,left,mid,right)showLog('--->'+getArrayString(datas))//显示数组中间状态endend//调用方法：procedureTForm1.btn1Click(Sender:TObject)varinArr:array[0..9]ofIntegerbeginCopyMemory(@inArr[0],@CTabls[0],SizeOf(Integer)*10)showLog('输入数据：'+getArrayString(inArr))MergeSort(inArr,0,High(inArr))showLog('输出数据：'+getArrayString(inArr))end

标准库sort实现了4种排序方法， 插入排序 、 堆排序 、 快排 和 归并排序 ，但是并没有暴露给用户接口。sort包会根据数据选择最优的排序方法(其实只使用了3种， 归并排序 除外)。

用户需要实现以下接口才能使用sort包的排序功能。

对于常用的类型( 整型切片 、 float64切片 、 String切片 )，sort包提供了内置的接口实现

使用举例如下：

举例如下：