目录

归并排序递归写法：

归并排序非递归写法：

   归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即 先使每个子序列有序，再 使子序列间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序递归写法：

using  namespace  std;
const int N = 1e5+10;
int n;
int arr[N];
int tmp[N];
void merge(int *arr,int L,int M,int R){
    int p1 = L,p2 = M+1,N = R-L+1,k = 0;
    //左组开头L,结束M;右组开头M+1，结束R
    // int *tmp = new int [N]; //辅助数组
    while (p1<=M && p2<=R){
        tmp[k++] = arr[p1]<=arr[p2]? arr[p1++]:arr[p2++];
        //这里比较操作写成<=才是稳定排序
    }//while退出了，说明p1或者p2有一个越界了，所以下面二个while只会执行一个
    while (p1<=M){
        tmp[k++] = arr[p1++];
    }
    while (p2<=R){
        tmp[k++] = arr[p2++];
    }
    //最后从tmp数组拷贝元素到arr中，注意arr开始下标是从L开始，tmp下标是从0开始
    for(k = 0;k=R){ //base case :如果L>R边界错误直接返回;L==R只有一个元素不需要排序直接返回
        return;
    }
    int mid = L+(R-L)/2;
    mergeSort(arr,L,mid);//左边递归调用mergeSort
    mergeSort(arr,mid+1,R);//右边递归调用mergeSort
    merge(arr,L,mid,R);//对有序左组和右组进行merge操作即可
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i = 0;i>arr[i];
    }
    mergeSort(arr,0,n-1);
    for(int i = 0;i 
归并排序非递归写法： 
using  namespace  std;
const int N = 1e5+10;
int n;
int arr[N];
int tmp[N];
void merge(int *arr,int L,int M,int R){
    int p1 = L,p2 = M+1,N = R-L+1,k = 0;
//    int *tmp = new int [N]; //辅助数组:可以在全局大的tmp，那么这里就不需要申请又释放了
    while (p1<=M && p2<=R){
        tmp[k++] = arr[p1]<=arr[p2]? arr[p1++]:arr[p2++];
    }
    while (p1<=M){
        tmp[k++] = arr[p1++];
    }
    while (p2<=R){
        tmp[k++] = arr[p2++];
    }
    for(k = 0;k=R) return;
    int step = 1;
    int N = R-L+1;
    while (step=R) break;
//M>R说明左组越界了,M==R说明只有左组没有右组,这二种情况都结束当前步数的merge
            //MN/2){
            break;
        }
        step = step*2; //步数变化
    }
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i = 0;i>arr[i];
    }
    mergeSort2(arr,0,n-1);
    for(int i = 0;i