归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并操作

算法描述

复杂度

与快速排序的比较

用途(1、排序 2、求逆序对数)

ht示例代码(C语言: Pascal 语言： Basic语言： 非递归算法（C++）： 二路归并排序 Pascal/Dephi 源代码)

算法复杂度

Pascal中的归并算法

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

归并操作

归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。

如　设有数列{6，202，100，301，38，8，1}

初始状态： [6] [202] [100] [301] [38] [8] [1] 比较次数

i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ]　3

i=2 [ 6 100 202 301 ] [ 1 8 38 ]　4

i=3　[ 1 6 8 38 100 202 301 ] 4

总计：　11次

算法描述

归并操作的工作原理如下：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

设定两个指针，最初位置分别为两个已经排序序列的起始位置

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针达到序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

复杂度

时间O(nlogn)

空间O(n)

与快速排序类似。

与快速排序的比较

归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.

用途

1、排序

（速度仅次于快速排序，但较稳定）

2、求逆序对数

具体思路是，在归并的过程中计算每个小区间的逆序对数，进而计算出大区间的逆序对数（也可以用树状数组来求解）

ht示例代码

归并排序

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

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

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

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

示例代码

C语言:

输入参数中，需要排序的数组为array[],起始索引为first，终止索引为last。调用完成后，array[]中从first到last处于升序排列。

void MergeSort(int array[], int first, int last)

{

int mid = 0;

if(first<last)

{

mid = (first+last)/2;

MergeSort(array, first, mid);

MergeSort(array, mid+1,last);

Merge(array,first,mid,last);

}

}

Pascal 语言：

type arrtype=array[1..500]of integer;

procedure MergeSort(arr:arrtype;first,last:integer);

var mid:integer;

begin

mid:=0;

if first<last then

begin

mid = (first+last)div 2;

MergeSort(arr, first, mid);

MergeSort(arr, mid+1,last);

Merge(arr,first,mid,last);

end;

end;

Basic语言：

Sub MergeSort(Array() As Integer,First As Integer,Last As Integer)

Dim mid As Integer = 0

If first<last Then

mid = (first+last)\\ 2

MergeSort(Array, first, mid);

MergeSort(Array, mid+1,last);

Merge(Array,first,mid,last);

End If

End 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);

}

非递归算法（C++）：

#include <iostream>

#include <ctime>

#include <cstring>

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(data+a+i+j, data+a+i,(length-i)*sizeof(int));

}

memcpy(data+a, temp, (i+j)*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 algrothem used " << e-s << " miliseconds."

<< endl;

delete data;

return 0; }

二路归并排序 Pascal/Dephi 源代码

：

　Const

FI = 'in.txt' ;

FO = 'out.txt' ;

MaxN = 10000 ;

Type

TIndex = Longint ;

TDat = Array [ 0 .. MaxN ] Of TIndex ;

Var

N : TIndex ;

Dat : TDat ;

Tmp : TDat ;

Procedure Merge ( L , Mid , R : TIndex ) ;

Var

P1 , P2 : TIndex ;

E1 , E2 : TIndex ;

P : TIndex ;

I : TIndex ;

Begin

P1 := L ;

P2 := Mid + 1 ;

P := L ;

Repeat

If ( Dat [ P1 ] <= Dat [ P2 ] ) Then

Begin

Tmp [ P ] := Dat [ P1 ] ;

Inc ( P1 ) ;

Inc ( P ) ;

End

Else

Begin

Tmp [ P ] := Dat [ P2 ] ;

Inc ( P2 ) ;

Inc ( P ) ;

End ;

Until ( P1 = Mid + 1 ) Or ( P2 = R + 1 ) ;

If ( P1 = Mid + 1 ) Then

Begin

E1 := P2 ;

E2 := R ;

End

Else

Begin

E1 := P1 ;

E2 := Mid ;

End ;

For I := E1 To E2 Do

Begin

Tmp [ P ] := Dat [ I ] ;

Inc ( P ) ;

End ;

End ;

Procedure Sort ( L , R : TIndex ) ;

Var

Mid : TIndex = 0 ;

Begin

Mid := ( L + R ) Shr 1 ;

If ( L < Mid ) Then

Sort ( L , Mid ) ;

If ( Mid + 1 < R ) Then

Sort ( Mid + 1 , R ) ;

Merge ( L , Mid , R ) ;

For Mid := L To R Do

Dat [ Mid ] := Tmp [ Mid ] ;

End ;

Procedure Init ;

Var

I : TIndex ;

Begin

FillChar ( Dat , SizeOf ( Dat ) , 0 ) ;

Readln ( N ) ;

For I := 1 To N Do

Read ( Dat [ I ] ) ;

End ;

Procedure Main ;

Begin

Sort ( 1 , N ) ;

End ;

Procedure Final ;

Var

I : TIndex ;

Begin

For I := 1 To N Do

Write ( Dat [ I ] , ' ' ) ;

Writeln ;

End ;

Begin

Assign ( Input , FI ) ;

Assign ( Output , FO ) ;

Reset ( Input ) ;

Rewrite ( Output ) ;

Init ;

Main ;

Final ;

Close ( Input ) ;

Close ( Output ) ;

End .

Delphi归并排序完整源代码例子：

//合并子函数

procedure TForm1.MergePass(var datas: array of Integer; left, mid,

right: Integer);

var

tmpArr:array of Integer;

arrLen:Integer;

i,k:Integer;

begin1,begin2,end1,end2:Integer;

begin

arrLen := right -left +1;

SetLength(tmpArr,arrLen);

begin1 := left;

end1 := mid;

begin2 := mid+1;

end2 := right;

k:=0;

while((begin1<=end1)and(begin2<=end2)) do

begin

if(datas[begin1]<datas[begin2]) then

begin

tmpArr[k]:=datas[begin1];

Inc(begin1);

end

else

begin

tmpArr[k]:=datas[begin2];

Inc(begin2);

end;

inc(k);

end;

while(begin1<=end1) do

begin

tmpArr[k] := datas[begin1];

Inc(begin1);

Inc(k);

end;

while(begin2<=end2) do

begin

tmpArr[k] := datas[begin2];

Inc(begin2);

Inc(k);

end;

for i := 0 to (right-left) do

begin

datas[left+i]:=tmpArr[i];

end;

end;

//排序主函数，left是数组左下标，0开始。right是数组右下标。

procedure TForm1.MergeSort(var datas: array of Integer; left, right: Integer);

var

mid:Integer;

i:Integer;

begin

mid:=0;

if(left<right) then

begin

mid:=(right+left) div 2;

showLog('中间索引：'+inttostr(mid));

MergeSort(datas,left,mid);

MergeSort(datas,mid+1,right);

MergePass(datas,left,mid,right);

showLog('--->'+getArrayString(datas)); //显示数组中间状态

end;

end;

//调用方法：procedure TForm1.btn1Click(Sender: TObject);

var

inArr:array[0..9] of Integer;

begin

CopyMemory(@inArr[0],@CTabls[0],SizeOf(Integer)*10);

showLog('输入数据：'+getArrayString(inArr));

MergeSort(inArr,0,High(inArr));

showLog('输出数据：'+getArrayString(inArr));

end;

算法复杂度

比较操作的次数介于(nlogn) / 2和nlogn - n + 1。 赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：Θ (n)

Pascal中的归并算法

所谓归并排序是指将两个或两个以上有序的数列（或有序表），合并成一个仍然有序的数列（或有序表）。这样的排序方法经常用于多个有序的数据文件归并成一个有序的数据文件。归并排序的算法比较简单。

基本思想方法是：

　（1）假设已经有两个有序数列，分别存放在两个数组s，r中；并设i，j分别为指向数组的第一个单元的下标；s有n个元素，r有m个元素。

（2）再另设一个数组a，k指向该数组的第一个单元下标。

（3）算法分析（过程）：

procedure merge(s,r,a,i,j,k);

begin

i1:=i;

j1:=j;

k1:=k;

while (i1<n) and (j1<m) do

if s[i1]<=r[j1] then

begin

a[k]:=s[i1];

i1:=i1+1;

k:=k+1;

end

else

begin

a[k]:=r[j1];

j1:=j1+1;

k:=k+1;

end;

while i1<=n do

begin

a[k]:=s[i1];

i1:=i1+1;

k:=k+1;

end;

while j1<=m do

begin

a[k]:=r[j1];

j1:=j1+1;

k:=k+1;

end;

end;

完整的C++源代码

　#include<iostream.h>

void Merge(int r[],int r1[],int s,int m,int t)

{

int i=s;int j=m+1;int k=s;

while(i<=m&&j<=t)

{

if(r[i]<=r[j])r1[k++]=r[i++];

else r1[k++]=r[j++];

}

if(i<=m)

while(i<=m) r1[k++]=r[i++];

else while(j<=t)

r1[k++]=r[j++];

for(int l=0;l<8;l++)

r[l]=r1[l];

}

void MergeSort(int r[],int r1[],int s,int t)

{

if(s==t)r1[s]=r[s];

else

{

int m=(s+t)/2;

MergeSort(r,r1,s,m);

MergeSort(r,r1,m+1,t);

Merge(r1,r,s,m,t);

}

}

void main()

{

int r[8]={10,3,5,1,9,34,54,565},r1[8];

MergeSort(r,r1,0,7);

for(int q=0;q<8;q++)

cout<<" "<<r[q];

}

end;

完整的JAVA源代码

public static int[] mergeSort(int[] data1,int[] data2)

{

int[] temp=new int[data1.length+data2.length];

int i=0,j=0,iter=0;

for(;i<data1.length&&j<data2.length;)

{

if(data1[i]<=data2[j])

{

temp[iter]=data1[i];

iter++;

i++;

}

else

{

temp[iter]=data2[j];

iter++;

j++;

}

}

for(;i<data1.length;i++,iter++)

{

temp[iter]=data1[i];

}

for(;j<data2.length;j++,iter++)

{

temp[iter]=data2[j];

}

return temp;

}

归并排序有两种实现方法：自底向上和自顶向下，算法实现如下：

1.自底向上算法

#include <stdio.h>

#include <time.h>

void Merge(int *a,int low,int mid,int high)

{

int i = low,j = mid + 1,k = 0;

int *temp = (int *)malloc((high - low + 1)*sizeof(int));

while(i <= mid && j <= high)

a[i] < a[j] ? (temp[k++] = a[i++]):(temp[k++] = a[j++]);

while(i <= mid)

temp[k++] = a[i++];

while(j <= high)

temp[k++] = a[j++];

memcpy(a + low,temp,(high -low + 1)*sizeof(int));

free(temp);

}

void MergeSort(int *a,int n)

{

int length;

for(length = 1;length < n;length *= 2)

{

int i;

for( i = 0;i + 2*length - 1 <= n - 1;i += 2*length)

Merge(a,i,i+length-1,i+2*length -1);

if(i + 2*length - 1 <= n - 1)//尚有两个子文件，其中后一个长度小于length

Merge(a,i,i +2* length -1,n - 1);

}

}

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 algrothem used " << e-s << " miliseconds."<< endl;

delete data;

return 0;

}

2.自顶向下

void Merge(int r[],int r1[],int s,int m,int t)

{

int i=s;int j=m+1;int k=s;

while(i<=m&&j<=t)

{

if(r[i]<=r[j])r1[k++]=r[i++];

else r1[k++]=r[j++];

}

while(i<=m) r1[k++]=r[i++];

while(j<=t)

r1[k++]=r[j++];

for(int l=0;l<8;l++)

r[l]=r1[l];

}

void MergeSort(int r[],int r1[],int s,int t)

{

if(s==t)r1[s]=r[s];

else{

int m=(s+t)/2;

MergeSort(r,r1,s,m);

MergeSort(r,r1,m+1,t);

Merge(r1,r,s,m,t);

}

}