递归实现

反复将当前区间[left,right]分为两半，

对两个子区间[left,mid]和[mid+1,right]分别递归进行归并排序，

然后将两个已经有序的子区间，合并，排序，返回

void 合并并排序(int *A,int L1,int R1,int L2,int R2){

        int i=L1,j=L2;

        int temp[maxn],index=0;//temp为临时数组用于存放当前两个子分区的排序结果，index为下标

        while(i<=R1&&j<=R2){//谁大把谁放进temp

            if(A[i]<=A[j]) temp[index++]=A[i++];

            else temp[index++]=A[j++];

        }

        //之前循环退出时，并未处理所有元素，分别试探看哪个还有剩余，也都放进去

        while(i<=R1) temp[index++]=A[i++];

        while(j<=R2) temp[index++]=A[j++];

        //把temp中的临时，放入原来数组

        for(int i=0;i<index;i++){

            A[L1+i]=temp[i];

        }

}

void mergeSort(int A[],int left,int right){

    if(left>=right) return;//返回条件，只剩一个元素

    int mid=(left+right)/2;

    mergeSort(A,left,mid);

    mergeSort(A.mid+1,left);

    合并并排序(A,left,mid,mid+1,right);

}

非递归实现

步长值初始为2

步长值增加

将数组中每步长值个元素分为一组，进行内部排序

把左step/2个元素，与右step/2个元素合并，

而，如果元素个数不超过step/2，则不操作。

void mergeSort(int A[]){

    for(int step=2;step/2<=n;step*=2){//多种步长

        for(int i=1;i<=n;i+=step){//每种步长，如果只要显示排序产生的结果，此处可以直接用sort

            int mid=i+step/2-1;//将每组分为两份，i从1开始，所以-1

            if(mid+1<=n){

                合并和排序(A,i,mid,mid+1,min(i+step-1,n));//min处理最后一种情况

            }

        }

    }

}

2路归并排序

递归实现

非递归实现