来自 block sort 的维基百科页面我发现块排序的工作原理是将初始数组分成长度为 16 的小子数组，例如，在 O(n) 时间内对所有这些子数组进行排序，然后以我无法理解的方式合并所有这些块。
例如，考虑一个长度为 16 的数组，将其分成 4 个块，每个块的长度为 4，并对这些块进行排序，我们得到:
10 1 8 3 4 19 20 13 14 17 8 9 12 18 7 20
10 1 8 3 ----- 4 19 20 13 ----- 14 17 8 9 ----- 12 18 7 20
1 3 8 10 ----- 4 13 19 20 ----- 8 9 14 17 ----- 7 12 18 20
谁能解释一下合并步骤是如何工作的？
最佳答案
通常归并排序更进一步，将数组分成 2 个块。为了合并，它会创建一个指向两个块的指针并比较它们的值。它选择较小的并增加相应的指针。
1 4 5 ...
^
2 3 4 ...
^
选择 1，因为它更小，并更新指针
1 4 5 ...
^
2 3 4 ...
^
选择 2
1 4 5 ...
^
2 3 4 ...
^
选择 3 等等....
这些值放在一个数组上，该数组将与使用相同技术创建的另一个数组进行比较。它继续合并，直到所有成员都被排序。我没有考虑您可以在真正的合并算法中进行的大量优化。
关于sorting - block 排序算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26946545/