【答案解析】问题描述：数组a[0，mid-1]和a[mid，n-1]是各自有序的，对数组a[0，n-1]的两个子有序段进行合并，得到a[0，n-1]整体有序。要求空间复杂度为O(1)(注：al[i]元素是支持"＜"运算符的)。假设给定数组a={1，5，6，7，9，2，4，8，10，13，14}，mid=5，a[0]～a[4]是有序的，a[5]～a[10]是有序的，合并后的数组为{1，2，4，5，6，7，8，9，10，13，14}。
假设数组中的两个子有序段都按升序排列，如上例所示。下面给出在这种情况下的实现思路。
由于限定空间复杂度为O(1)，因此不能使用归并方法。最容易想到的就是插入排序方法，这种算法的时间复杂度为O(n^2)，空间复杂度为O(1)，能满足题目要求，但是由于插入排序方法没有用到“数组a[0，mid-1]和a[mid，num-1]是各自有序的”这个条件，因此这种算法肯定不是最好的算法，下面给出另外一种方法。
实现思路：首先，遍历数组中下标为0～mid-1的元素，将遍历到的元素的值与a[mid]进行比较，当遍历到a[i](0＜=i＜=mid-1)时，如果满足a[mid]＜a[i]，那么交换a[i]与a[mid]的值。接着找到交换后的a[mid]在a[mid，num-1]中的具体位置(在a[mid，num-1]中进行插入排序)，实现方法为：遍历a[mid～num-2]，如果a[mid+1]＜a[mid]，那么交换a[mid]与a[mid+1]的位置。实现代码如下：
public class Test{
public static void findRightPlaceForMid(int a[], int mid){
int len=a.length;
int tmp;
for(int i=mid; i＜len-1; i++){
if(a[i+1]＜a[i]){
tmp=a[i];
a[i]=a[i+1];
a[i+1]=tmp;
}
}
}
public static voidsort(int a[], int mid){
int tmp;
for(int i=0; i＜=mid-1; i++){
if(a[mid]＜a[i]){
tmp=a[i];
a[i]=a[mid];
a[mid]=tmp;
findRightPlaceForMid(a, mid);
}
}
}
public static voidmain(String[]args){
int a[]={1, 5, 6, 7, 9, 2, 4, 8, 10, 13, 14};
sort(a, 5);
fnr(int i=0; i＜11; i++)
System.out.print(a[i]+"");
}
}
程序运行结果为：
1 2 4 5 6 7 8 9 10 13 14
在实现时需要注意的问题是：题目中给出了“al[i]元素是支持＜"运算符的”这一限制条件，因此，在程序中只能出现形如“a[i]＜a[j]”的表达式，最好不要出现“a[j]＞a[i]”这种写法。
引申：
1)如果数组中两个子有序段都按降序排列，可以用类似的方法来解决。
2)如果其中一个子序段按升序排列，另外一个子序段按降序排列，可以首先对其中一个子序段进行逆序，然后采用上面介绍的方法进行排序。