学步园

给定长度分别为n和m的两个各自有序数组X，Y，以及一个长度为n的辅助数组A，存在O(m+n)时间复杂度的算法AuxSort;该算法可以原地归并排序X和Y，同时A中元素保持不变(顺序可能打乱)

AuxSort算法具体步骤如下：

交换X 和 A。
维护两个整数下标 px, py，初始化为0，分别代表A[0]和Y[0]; 另外维护一个dest指针，初始化指向X[0]，并且该指针在移动到X[n-1]后，自动过渡到Y[0]。
比较A[px], Y[py]：
若 A[px] <= Y[py],   swap(A[px++], *dest++); 
若 A[px]  >  Y[py]，swap(Y[py++], *dest++);

若A或Y中仍有剩余元素，则将剩余部分依次与*dest交换。当然每一步要执行dest++操作。

// 把数组向右旋转，
//a[s]...a[mid],a[mid+1]...a[e]
// a[mid+1]...a[e], a[s]...a[mid]
void RightRotate(int* a ,int s, int mid, int e)
{
   if(a ==NULL || s > mid || e < mid || s > e) return;
   
   for(int i=s,j=mid; i<j; i++,j--)
   swap(a[i],a[j]);
   for(int i=mid+1,j=e; i<j; i++,j--)
   swap(a[i],a[j]);   
   for(int i=s,j=e ; i<j ; i++,j--)
   swap(a[i],a[j]);   
}
void display(int* a,int s,int e)
{
  for(int i=s;i<=e;i++)
  cout<<a[i]<<" ";
  cout<<endl;     
}
//时间O(n),空间O(1),原地归并 
//数组a[s]..a[mid] 升序，a[mid+1]...a[e]也是升序
//求合并后a[s].....a[e]升序 
void merge(int a[], int s,int mid, int e)
{
  if(a ==NULL || s > mid || e < mid || s > e) return;
  int left = s;
  int right =mid+1;    
  while(left < e)
  {
      display(a,0,7);
     //只要左边是最小的，直接加入 
     while(a[left] <= a[right])left++;
     
     int start = right;
     //在右边找到第一个比 a[left]大的 
     while(right<=e && a[left] > a[right]) right++;
     //右旋转 这段序列 
     RightRotate(a ,left, start-1, right-1);
     //此时 right -start 个元素已排好序 
     left += right - start;   
      
  }
}
int main()
{
  
     int a[]={3,5,7,9,2,3,4,10};
     merge(a, 0,3, 7);
     display(a,0,7);
     system("pause");
     return 0;
}