algorithm - 算法中的pass是什么意思？

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 个游程。每次遍历都会合并偶数和奇数游程，使游程大小加倍(除了最后一次运行可能会更短)。当运行大小 >= 元素数时排序完成。

|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