1. 问题

二分归并排序：对n个不同的数构成的数组A[1….n]进行排序，其中n=2^k.

2. 解析

二分归并排序：

将一个数组分割，分割成两个部分，递归分割下去，直到剩余数组元素个数不满足分割条件，就将分割的数组进行排序，然后在递归上去，将分割的序列形成的有序数组进行合并，最后形成一个有序的数组。具体例子如下图：

递归分组函数：

int MergeSort(int A[],int l,int r){

if(l<r){

mid=(l+r)/2;

MergeSort(A,l,mid);

MergeSort(A,mid+1,r);

Merge(A,l,mid,r);

}

合并函数

void Merge(int A[], int l, int mid, int r)

{

int *L, *R,x,y;

x=mid-l+1,y=r-mid;

L = (int*)malloc(sizeof(int)*x);

R = (int*)malloc(sizeof(int)*y);

int i ,j;

for (i=0; i <x; i++)

L[i] = A[i +l];

for (j=0; j < y; j++)

R[j] = A[j + mid + 1];

i = j = 0;

int k = l;

while (i <x && j <y)

{

if (L[i] <= R[j])

A[k++] = L[i++];

else

A[k++] = R[j++];

}

while (i < x)

A[k++] = L[i++];

while (j <y)

A[k++] = R[j++];

free(L);

free(R);

}