题目：数组al[0,mid-1]和al[mid,num-1]是各自有序的，对数组al[0,num-1]的两个子有序段进行merge，得到al[0,num-1]整体有序。要求空间复杂度为O(1)。注：al[i]元素是支持'<'运算符的。

分析

 

代码实例：

#include
      
       #include
       
        #include
        
         using namespace std;void MergeSort(int arry[],int len){    int left=0;    int mid=len/2;    int right=mid;    while(left
         
          
           arry[mid])        {            while(arry[right]
          
         
        
       
      

 

新的解体思路

设定两个指针left和right，初始状态下分别指向两个排序数组的首元素，

然后比较a[left]和a[right]大小，

1. 如果a[left]<=a[right]，那么数组中元素位置不发生改变，然后left往前进一步。
2. 如果a[left]>a[right]，则表明前半段元素中存在大于后半段的元素，那么我们将后半段这个小的元素移到前半段来。但是在移动之前，我们得为这个元素空留出地方。这就有了元素移动的操作。比如{1,3,5,7,2,4,6,8,10}这样子序列，我们发现后半段的2小于前半段的3，那么我们将2放入临时变量temp中，然后将{3,5,7}往后移动一个位置，然后将空出来的位置放入temp的值。
3. 这里总体的循环是while(left<right&&right<len)

代码实现

void mergesort2(int arry[],int len){    int mid=len/2;    int left=0;    int right=mid;    while(left
      
       
        left;i--)            {                arry[i]=arry[i-1];            }            arry[left]=temp;        }        PrintArry(arry,len);        cout<
        
         <<" "<
         
          <
         
        
       
      

上面程序的输出结果是

1 3 5 7 2 4 5 8 101 41 2 3 5 7 4 5 8 101 51 2 3 5 7 4 5 8 102 51 2 3 5 7 4 5 8 103 51 2 3 4 5 7 5 8 103 61 2 3 4 5 7 5 8 104 61 2 3 4 5 7 5 8 105 61 2 3 4 5 5 7 8 105 71 2 3 4 5 5 7 8 106 71 2 3 4 5 5 7 8 107 7