【答案解析】插入排序的基本思想是逐个将待排序元素插入到已排序的有序表中。假设n个待排序元素存储在数组R[n+1]中(R[0]预留)，则：
(1)初始时数组R[1..1]中只包含元素R[1]，则数组R[1..1]必定有序。
(2)从i=2到n，执行步骤(3)。
(3)此时，数组R被划分成两个子区间，分别是有序区间R[1..i-1]和无序区间R[i..n]，将当前无序区间的第1个记录R[i]插入到有序区间R[1..i]中适当的位置上，使R[1..i]变为新的有序区间。
在实现的过程中，设置监视哨R[0]，并从R[i-1]到R[0]查找元素R[i]的插入位置。
那么用插入排序对数组＜3，1，4，1，5，9，6，5＞进行排序的过程为：
那么整个排序过程需要比较的次数为12次。
归并排序的思想是将两个相邻的有序子序列归并为一个有序序列，然后再将新产生的相邻序列进行归并，当只剩下一个有序序列时算法结束。其基本步骤如下。
(1)将n个元素的待排序序列中每个元素看成有序子序列，对相邻子序列两两合并，则将生成[n/2]个子有序序列，这些子序列中除了最后一个子序列长度可能小于2外，其他的序列长度都等于2。
(2)对上述[n/2]个长度为2的子序列再进行相邻子序列的两两合并，则产生[n/4]个子有序序列，同理，只有最后一个子序列的长度可能小于4。
|
名 称
|
监视哨
|
序 列
|
说 明
|
|
原元素序列：
|
|
(3)，1，4，1，5，9，6，5
|
|
|
第1趟排序：
|
3
|
(1，3)，4，1，5，9，6，5
|
1插入时与3比较1次
|
|
第2趟排序：
|
4
|
(1，3，4)，1，5，9，6，5
|
4插入时与3比较1次
|
|
第3趟排序：
|
1
|
(1，1，3，4)，5，9，6，5
|
1插入时比较3次
|
|
第4趟排序：
|
5
|
(1，1，3，4，5)，9，6，5
|
5插入时与4比较1次
|
|
第5趟排序：
|
9
|
(1，1，3，4，5，9)，6，5
|
9插入时与5比较1次
|
|
第6趟排序：
|
6
|
(1，1，3，4，5，6，9)，5
|
6插入时与9和5分别比较1次
|
|
第7趟排序：
|
5
|
(1，1，3，4，5，5，6，9)
|
5插入时与9、6、5分别比较1次
|
(3)第i趟归并排序为，对上述[n/i]个长度为i的子序列两两合并，产生[n/2i]个长度为2i的子有序序列。 (4)重复执行此步骤，直到生成长度为n的序列为止。 那么用归并排序对数组＜3，1，4，1，5，9，6，5＞进行排序的过程为：
|
名 称
|
序 列
|
说 明
|
|
原元素序列：
|
3，1，4，1，5，9，6，5
|
|
|
第1趟排序：
|
[1，3]，[1，4]，[5，9]，[5，6]
|
比较4次
|
|
第2趟排序：
|
[1，1，3，4]，[5，5，6，9]
|
前半部分比较3次，后半部分比较3次
|
|
第3趟排序：
|
[1，1，3，4，5，5，6，9]
|
5分别与1、1、3、4比较一次
|
所以整个排序过程需要比较的次数为12次。