归并排序(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;
}