归并排序(merge sort)算法实现

归并排序(merge sort)体现了分治的思想，即将一个待排序数组分为两部分，对这两个部分进行归并排序，排序后，再对两个已经排序好的数组进行合并。这种思想可以用递归方式很容易实现。归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。

实现代码如下：

#include<stdio.h>

#include"common.h"

voidmerge(intdata[],intp,intq,intr)

{

inti,j,k,n1,n2;

n1=q-p+1;

n2=r-q;

intL[n1];

intR[n2];

for(i=0,k=p;i<n1;i++,k++)

L[i]=data[k];

for(i=0,k=q+1;i<n2;i++,k++)

R[i]=data[k];

for(k=p,i=0,j=0;i<n1&&j<n2;k++)

{

if(L[i]>R[j])

{

data[k]=L[i];

i++;

}

else

{

data[k]=R[j];

j++;

}

}

if(i<n1)

{

for(j=i;j<n1;j++,k++)

data[k]=L[j];

}

if(j<n2)

{

for(i=j;i<n2;i++,k++)

data[k]=R[i];

}

}

voidmerge_sort(intdata[],intp,intr)

{

if(p<r)

{

intq=(p+r)/2;

merge_sort(data,p,q);

merge_sort(data,q+1,r);

merge(data,p,q,r);

}

}

voidtest_merge_sort()

{

intdata[]={44,12,145,-123,-1,0,121};

printf("-------------------------------mergesort----------------------------\n");

out_int_array(data,7);

merge_sort(data,0,6);

out_int_array(data,7);

}

intmain()

{

test_merge_sort();

return0;

}