归并排序算法

把待排序序列分成相同大小的两个部分，依次对这两部分进行归并排序，完毕之后再按照顺序进行合并。

基本分治：将原问题分解为规模小的相对独立的子问题，在出口直接解决，然后递归，将子问题的解合并

intb[100];//辅助用的临时存储数组

voidMerge(inta[],intleft,intmid,intright)

{

inti=left,j=mid+1,k=left;

while(i<=mid&&j<=right){

if(a[i]<a[j])b[k++]=a[i++];

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

}

while(i<=mid)b[k++]=a[i++];

while(j<=right)b[k++]=a[j++];

for(k=left;k<=right;k++){

a[k]=b[k];

}

}

voidMergeSort(inta[],intleft,intright)

{

if(left<right){

intmid=(left+right)/2;

MergeSort(a,left,mid);

MergeSort(a,mid+1,right);

Merge(a,left,mid,right);

}

}