歸并排序(Merge Sort)，是非常好的一種排序方式。時間復雜度為O（nlogn)。空間復雜度為O(n)
同快速排序相比，其有穩定性以及最差情況下為O(nlogn)等特點。
歸并排序是典型的分而治之方法，首先將排序任務分成自任務，即Divide過程，然后將各個子任務初步完成(Conquer)，最后將所有的子任務合并(merge)就完成了整個任務。
整個算法框架如下：
void mergesort(int A[],int p,int r)
{
if(p<r)
{
int q=(p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
}
在merge中，首先將p->q的(q-p+1)個放到一個左邊的數組L中，將q+1->r的(r-q)個放到右邊的數組R中，然后將數組L和數組R的數按順序放置到A中。
void merge(A,p,q,r)
{
//construct the L and R array
int left=q+1-p;
int right = r-q;
int* L=new int[left];
int* R = new int[right];
//fill the L and R array
int i,j,k;
for(i=0;i<left;i++)
L[i]=A[p+i];
for(j=0;j<right;j++)
R[j]=A[q+j+1];
//copy the value from L and R to A
//Notice there are three cases
for(k=0,i=0,j=0;(i<left)&&(j<right);k++)
{
if(L[i]<=R[j])
{
A[p+k]=L[i];
i++;
}
else
{
A[p+k]=R[j];
j++;
}
}
if(i<left)
{
for(;i<left;i++,k++)
A[p+k]=L[i];
}
if(j<right)
{
for(;j<right;j++,k++)
A[p+k]=R[j];
}
//delete the L and R
delete [] L;
delete [] R;
}
整個mergesort的可執行代碼如下：
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstdlib>
#include <time.h>
#include <windows.h>
#define MAXSIZE 100
int arr[MAXSIZE];
using namespace std;
void print(bool flag=true)
{
if(flag)
{
copy(arr,arr+MAXSIZE,ostream_iterator<int>(cout," "));
cout<<endl;
}
}
void merge(int A[],int p,int q,int r)
{
int left = q-p+1;
int right = r-q;
int* L=new int[left];
int* R = new int[right];
int i,j,k;
for(i=0;i<left;i++)
L[i]=A[p+i];
for(j=0;j<right;j++)
R[j]=A[q+j+1];
for(k=0,i=0,j=0;(i<left)&&(j<right);k++)
{
if(L[i]<=R[j])
{
A[p+k]=L[i];
i++;
}
else
{
A[p+k]=R[j];
j++;
}
}
if(i<left)
{
for(;i<left;i++,k++)
A[p+k]=L[i];
}
if(j<right)
{
for(;j<right;j++,k++)
A[p+k]=R[j];
}
delete [] L;
delete [] R;
}
void mergesort(int A[],int p, int r)
{
if(p<r)
{
int q = (p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
}
int main(int argc,char* argv[])
{
int size = MAXSIZE;
for(int i=0;i<size;i++)
{
arr[i] = rand()%MAXSIZE;
}
print();
DWORD start = timeGetTime();
mergesort(arr,0,MAXSIZE-1);
DWORD end = timeGetTime();
print();
cout<<end-start<<endl;
system("pause");
return 0;
}