从维基百科关于块排序的页面(http://en.wikipedia.org/wiki/Sorting_algorithm)中,我了解到块排序通过将初始数组分成长度为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
请问有人能解释一下合并步骤的工作原理吗?