1．程序执行。我们第一次调用“MergePass（L.r,TR,k,L.length）;”，此时L.r是初始无序状态，TR为新申请的空数组，k=1.length=9。
2．第5～9行，循环的目的就两两归并，因s=1，n‐2×s+1=8，为什么循环i从1到8，而不是9呢？就是因为两两归并，最终9条记录定会剩下来，无法归并。
3．第7行，Merge函数我们前面已经详细讲过，此时i=1，i+s‐1=1，i+2×s‐1=2。也就是说，我们将SR（即L.r）中的第一个和第二个记录归并到TR中，然后第8行，i=i+2×s=3，再循环，我们就是将第三个和第四个记录归并到TR中，一直到第七和第八个记录完成归并，如图9‐8‐14所示。
（点击查看大图）图9-8-14
4．第10～14行，主要是处理最后的尾数，第11行是说将最后剩下的多个记录归并到TR中。不过由于i=9，n‐s+1=9，因此执行第13～14行，将20放入到TR数组的最后。
（点击查看大图）图9-8-15
5．再次调用MergePass时，s=2，第5～9行的循环，由第8行的i=i+2×s可知，此时i就是以4为增量进行循环了，也就是说，是将两个有两个记录的有序序列进行归并为四个记录的有序序列。最终再将最后剩下的第九条记录“20”插入TR。
（点击查看大图）图9-8-16
6．后面的类似，略。
非递归的迭代方法，避免了递归时深度为log2n的栈空间，空间只是用到申请归并临时用的TR数组，因此空间复杂度为O(n)，并且避免递归也在时间性能上有一定的提升，应该说，使用归并排序时，尽量考虑用非递归方法。9
注：9关于归并排序算法更详细讲解，请参考《算法导论》第一部分第2章“算法入门”的2.3.1节“分治法”的内容。