一、题目理解
题目：数组al[0,mid-1]和al[mid,num-1]是各自有序的，对数组al[0,num-1]的两个子有序段进行merge，得到al[0,num-1]整体有序。要求空间复杂度为O(1)。注：al[i]元素是支持'<'运算符的。
数据结构第一章就讲了有序表合并，不过那时候是合并到新表，判断条件是while(i<len1||j<len2)，然后把a1或者a2数组(只有一个，因为另一个必定已经完全插入进了c数组，这也是为什么while条件是“或”)后面的元素；如果数据结构老师足够负责的话就应该提到这种情况，或者讲讲；不过由此来看，BAT的面试题很多还是来自课本的。
二、算法实现
设定两个指针left和right，初始状态下分别指向两个排序数组的首元素，然后比较a[left]和a[right]大小，如果a[left]<=a[right]，那么数组中元素位置不发生改变，然后left往前进一步。如果a[left]>a[right]，则表明前半段元素中存在大于后半段的元素，那么我们将后半段这个小的元素移到前半段来。但是在移动之前，我们得为这个元素空留出地方。这就有了元素移动的操作。比如{1,3,5,7,2,4,6,8,10}这样子序列，我们发现后半段的2小于前半段的3，那么我们将2放入临时变量temp中，然后将{3,5,7}往后移动一个位置，然后将空出来的位置放入temp的值。这里总体的循环是while(left<right&&right<len)。
做这个题，我首先确实想到了插入排序，不过结合ACM，我想到插入排序需要移动元素，这样时间复杂度可能比较高，不能AC(ACM对我的影响太大了)，我立马排除了这种想法，哎，只需要考虑空间复杂度的。
package a;
public class Test1 {
static int[] a = {1,3,5,7,9,0,2,4,6,8};
public static void main(String[] args) {
// TODO Auto-generated method stub
solve(a,4,9);
for(int i:a) {
System.out.print(i+" ");
}
System.out.println();
}
private static void solve(int[] a, int mid, int num) {
// TODO Auto-generated method stub
int i=0;
int j=mid+1;
/*
* 原来条件我加上了i<=mid,没加i<j，这样是完全错误的；因为我们移动元素了，所以前半段不能限制到mid；
* 我认为i<j是应该想到的，只需要这一个就够了，如果我每天都还AC的话或许就会记得这个条件。
*/
for(i=0,j=mid+1;i<j&&j<=num;) {
if(a[i]<=a[j]) {
i++;
}else {
int tempVal = a[j];
for(int k=j-1; k>=i; k--) {
a[k+1] = a[k];
}
a[i] = tempVal;
j++;
/*
* 这个自加条件不能放到if else后面，这样的话如果if里面i++了，然后又i++了
*/
i++;
}
}
}
}
