算法中的遍是什么意思？

Question

我遇到了一道来自 GATE PYQ 的练习题。 该问题询问合并排序算法中的pass。下面是问题：

如果使用直接双向归并排序算法对以下元素进行升序排序：

 20, 47, 15, 8, 9, 4, 40, 30, 12, 17

那么在算法第二次通过后这些元素的顺序是：

A) 8, 9, 15, 20, 47, 4, 12, 17, 30, 40

B) 8, 15, 20, 47, 4, 9, 30, 40, 12, 17 [正确选项]

C) 15, 20, 47, 4, 8, 9, 12, 30, 40, 17

D) 4, 8, 9, 15, 20, 47, 12, 17, 30, 40

在这种情况下，我无法弄清楚 pass 的含义以及如何找到它。

元素在递归调用中的分布：

         20, 37, 15, 8, 9, 4, 40, 30, 12, 17
                 /                 \
        20, 47, 15, 8, 9       4, 40, 30, 12, 17
       /        \                     /          \
 20, 47, 15     8, 9              4, 40, 30      12, 17
    /    \
20, 47   15

排序后：

           4 ,8, 9, 15, 12, 17, 20, 30, 40, 47 
                 /                     \
     8, 9, 15, 20, 47               4, 12, 17, 30, 40
       /        \                     /          \
 20, 15, 47     8, 9              4, 30, 40      12, 17
    /    \
20, 47   15

Answer 1

术语 pass 的使用意味着该问题询问的是自下而上的合并排序，它首先将 n 个元素的数组视为大小为 1 的 n 运行s。每个 pass 合并偶数和奇数运行s，将运行s 的大小加倍（最后一个运行除外，它可能更短）。当运行大小 >= 元素数量时完成排序。

|20|47|15| 8| 9| 4|40|30|12|17|   start
|20 47| 8 15| 4  9|30 40|12 17|   after pass 1
| 8 15 20 47| 4  9 30 40|12 17|   after pass 2
| 4  8  9 15 20 30 40 47|12 17|   after pass 3
| 4  8  9 12 15 17 20 30 40 47|   after pass 4, done

算法中的遍是什么意思？

What is meant by a pass in an Algorithm?

sorting

algorithm

recursion

mergesort