合并排序中用到的子函数 merge()，功能是合并两个有序的子数组，其算法如下：输入：整数数组 A[]，下标 p,q,r,元素个数 mA[p]~A[q]及 A[q+1]~A[r]已按递增顺序排序输出：按递增顺序排序的子数组 A[p]~A[r]题意：合并两个递增子数组题意：合并两个递增子数组 A[p]~A[q]A[p]~A[q]及及 A[q+1]~A[r]A[q+1]~A[r]，合并后按递，合并后按递增顺序排序增顺序排序1.void merge(int A[],int p,int q,int r,int m)2.{3.int *bp=new int[m]；分配缓冲区，存放被排序的元素分配缓冲区，存放被排序的元素4.int i,j,k;5.i=p;j=q+1;k=0;i i 表示子数组表示子数组 A[p]~A[q]A[p]~A[q]中当前元素所在的位置；中当前元素所在的位置；j j 表示子数组表示子数组A[q+1]~A[r]A[q+1]~A[r]中当前元素所在的位置中当前元素所在的位置6.while(i<=q较大的元素后装入临时数组较大的元素后装入临时数组 bp[]bp[]11.}12.if(i==q+1)如果子数组如果子数组 A[p]~A[q]A[p]~A[q]中的元素已经全部装入临时数组中的元素已经全部装入临时数组 bp[]bp[]（先装（先装入的是较小的元素）入的是较小的元素）13.{for(;j<=r;j++)14.bp[k++]=A[j];}那么就将子数组那么就将子数组 A[q+1]~A[r]A[q+1]~A[r]中剩下的元素全部装入临时数组中剩下的元素全部装入临时数组 bp[]bp[]15.else否则一就定是子数组否则一就定是子数组 A[q+1]~A[r]A[q+1]~A[r]中的元素已经全部装入临时数组中的元素已经全部装入临时数组bp[]bp[]（先装入的是较小的元素）（先装入的是较小的元素）16.{for(;i<=q;i++)17.bp[k++]=A[i];}于是，将子数组于是，将子数组 A[p]~A[q]A[p]~A[q]中剩下的元素全部装入临时数组中剩下的元素全部装入临时数组 bp[]bp[]18.k=0;为将临时数组为将临时数组 bp[k++]bp[k++]中元素复制到中元素复制到 A[i]A[i]做准备，从第做准备，从第 0 0 个元素开个元素开始复制始复制19.for(i=p;i<=r;i++)20.A[i]=bp[k++];将临时数组将临时数组 bp[k++]bp[k++]中元素复制到中元素复制到 A[i]A[i]21.delete bp;收回缓冲区收回缓冲区22.}。