【答案解析】[解法1] (1)算法基本设计思想：
①把数组的前m个元素看成一个归并段，后n个元素看成一个归并段，增加一个临时数组B[1..m+n]存储临时归并结果。分别设置两个指针k1，k2，指向两个归并段首元素，再设置一个指针k3指向临时数组下一个结果位置。
②如果1≤k1≤m而且m+1≤k2≤m+n执行③；否则执行④。
③比较两个归并段指针所指元素的大小。如果A[k1]≤A[k2]，那么B[k3++]=A[k1++]；否则B[k3++]=A[k2++]。执行②。
④如果k1＞m，则第二个归并段的元素还未比较完，把第二个归并段的剩余元素复制到数组B。如果k2＞m+n，则第一个归并段的元素还未比较完，把第一个归并段的剩余元素复制到数组B。最后把数组B复制到数组A。
(2)算法的实现如下：
void Merge(int[]A){ //实现数组1-m和m+1-m+n两个归并段归并。
int B[m+n+1]; //临时辅助数组B[1..m+n]
int k1, k2, k3;
k1=1; k2=m+1; k3=1; //3个指针
while(k1＜m&&k2＜=m+n){ //如果两个归并段都没有比较完
if(A[k1]＜=A[k2])B[k3++]=A[k1++]; //第一个归并段指针指向元素较小
else B[k3++]=A[k2++]; //第二个归并段指针指向元素较小
}
if(k1＞m) //把没有比较完的归并段中的剩余元素复制到数组B
while(k2＜=m+n) B[k3++]=A[k2++];
else
while(k1＜=m) B[k3++]=A[k1++];
for(int i=1; i＜=m+n; i++) //把临时数组B复制到A数组
A[i]=B[i];
}
(3)总共遍历了A数组两遍，第一遍合并，第二遍复制结果，时间复杂度为O(m+n)。临时数组B空间大小m+n，所以空间复杂度为O(m+n)。
[解法2] (1)算法的基本设计思想：
将数组A看成是两个长度分别为m和n的有序表L1和L2，只需要将L2中的每个元素依次向前插入到前面有序数组部分中的合适位置即可。插入过程如下：
①取表L2中的第一个元素A[m+1]，暂存在temp中，让temp前插到合适的位置。
②重复过程①，继续插入A[m+2]，A[m+3]，…，A[m+n]，直到数组A整体有序。
(2)算法的实现如下：
void InsertSort(int A[], int m, int n){
int temp; //辅助变量，暂存待插入元素
for(int i=m+1; i＜=m+n; i++){ //将L2中的元素依次插入到前面有序部分
temp=A[i];
for(int j=i-1; j＞=1&&temp＜a[j]; j--) //向前查找待插入位置
A[j+1]=A[j]; //向后挪位
A[j+1]=temp; //复制到插入位置
}
}
(3)本算法的时间复杂度由m和n共同决定，最内层循环的A[j+1]=A[j]为基本语句。在最坏情况下，即L2中的所有元素均小于L1中的最小元素，则对于L2中的每个元素，为了找到其插入位置都需要做m次移动，故时间复杂度为O(mn)。空间复杂度为O(1)。