原地归并排序 Merge Sort in place - c++编程基础

师姐给身边的某小朋友出了道题：O(1)空间复杂度实现归并排序

在草纸上笔画了一下，20分钟编码调试

思路是：merge的时候，merge(arr, l, m, n)在 l m+1处放 i j指标，

循环i直到m 若arr[j]>arr[i] 则右移 i-m的元素 j++ m++

简单修改使用模板就可以扩展到多种arr类型，以下简单以数组为例

#include   
using namespace std;  
  
void merge(int* arr, int l, int m, int n){  
    int i=l, j=m+1;  
    while(i<=m && j<=n){  
        if(arr[i]>




arr[j]){//向右平移左半部分  
            int tmp = arr[j];  
            for(int t=j; t>i; t--)   
               arr[t]=arr[t-1];  
            arr[i] = tmp;  
            ++m;  
            ++j;  
        }  
        ++i;  
    }  
}  
  
void mergeSort(int* arr, int l, int n){  
    if(l