c - 合并排序过程说明(自上而下，自下而上)

Question

元素的合并排序过程步骤是什么:20 47 15 8 9 4 40 30 12 17

我遇到过这个......

Pass1: |20 47| |8 15| |4 9| |30 40| |12 17|

Pass2: |8 15 20 47| |4 9 30 40| |12 17|

现在的困惑是 Pass3 和 Pass4 是什么？ (在 Pass3 中组合 quads 或 pair+quad)还有，这种方法是自上而下还是自下而上？

Answer 1

这些是自下而上归并排序的过程。包含 10 个元素的数组被视为每个包含 1 个元素的 10 个子数组，并进行排序，因为每个子数组只有 1 个元素。有n-1个合并操作(n/2+n/4+n/8+...)。

 20 47 15  8  9  4 40 30 12 17    initial array 
|20|47|15| 8| 9| 4|40|30|12|17|   consider as 10 sub arrays of size 1
|20 47| 8 15| 4  9|30 40|12 17|   pass 1, 5 merges
| 8 15 20 47| 4  9 30 40|12 17|   pass 2, 2 merges
| 4  8  9 15 20 30 40 47|12 17|   pass 3, 1 merge
| 4  8  9 12 15 17 20 30 40 47|   pass 4, 1 merge

维基文章:

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation

请注意，尽管大多数类类型的合并排序都是自上而下的，但大多数实际图书馆使用自下而上合并排序的一些变体。

这将是自上而下合并排序的操作顺序，深度优先，左侧优先。假设一个优化的自上而下合并排序使用索引来拆分子数组，由于子数组的递归拆分，n-1 对索引被生成并存储在堆栈中，对应于发生的 n-1 合并操作典型的 2 路归并排序。请注意，直到通过递归拆分创建两个大小为 1 的子数组的第一个实例时，合并才会开始。然后拆分和合并继续向下和向上调用堆栈，深度优先，左侧优先。

对于本例中的10个元素，有10-1=9次拆分和合并操作。

 20 47 15  8  9  4 40 30 12 17 
|20 47 15  8  9| 4 40 30 12 17|  lvl 0 split
|20 47|15  8  9|                 lvl 1 split
|20|47|                          lvl 2 split
|20|                             lvl 3 size == 1
   |47|                          lvl 3 size == 1
|20 47|                          lvl 2 merge
      |15| 8  9|                 lvl 2 split
      |15|                       lvl 3 size == 1
         | 8| 9|                 lvl 3 split
         | 8|                    lvl 4 size == 1
            | 9|                 lvl 4 size == 1
         | 8  9|                 lvl 3 merge
      | 8  9 15|                 lvl 2 merge
| 8  9 15 20 47|                 lvl 1 merge
               | 4 40|30 12 17|  lvl 1 split
               | 4|40|           lvl 2 split
               | 4|              lvl 3 size == 1
                  |40|           lvl 3 size == 1
               | 4 40|           lvl 2 merge
                     |30|12 17|  lvl 2 split
                     |30|        lvl 3 size == 1
                        |12|17|  lvl 3 split
                        |12|     lvl 4 size == 1
                           |17|  lvl 4 size == 1
                        |12 17|  lvl 3 merge
                     |12 17 30|  lvl 2 merge
               | 4 12 17 30 40|  lvl 1 merge
| 4  8  9 12 15 17 20 30 40 47|  lvl 0 merge

自下而上合并排序通过将 n 个元素的数组视为每个 1 个元素的 n 个子数组来跳过所有递归拆分，并立即开始合并过程，通过迭代根据需要生成索引。对于大型数组，大部分时间都花在合并上，自上而下和自下而上都是一样的，在这种情况下自上而下并不比自下而上慢多少，但是大多数库会实现一些自下而上合并的变体像 std::stable_sort 这样的排序。