一趟归并排序问题，归并前的子表们，最后一个子表的开始下标

Question

Merge算法实现了一次归并，接下来用Merge算法解决一趟归并的问题。
某一趟归并排序中，设各子表的长度为length（最后一个子表的长度可能小于length），则归并前R[0……n-1]中共有⌈n/length⌉个有序子表，到这里都非常好理解。

教材上给出，这几个子表为：
R[0……length-1]
R[length……2length-1]
……
R[(⌈n/length⌉)×length……n-1]

为什么最后一个子表的初始下标是(⌈n/length⌉)×length
为什么不是(⌈n/length⌉-1)×length？
——
我的理解:比如说把10个元素分成长度为2的5组，第一组是0-1，开始下标是(1-1)×2
第二组是2-3，开始下标是(2-1)×2
也就是第m（序列号）组，的开始下标应该是(m序列号-1)×2
那么最后一组的序列号应该是个数，也就是 (⌈n/length⌉)
为什么不需要－1呢？
——
按照(⌈n/length⌉)×length
可以整除的情况:取n=16，length＝4
(⌈n/length⌉)×length不就等于4×4了吗？？最后一个子表的下标怎么可能从16开始呢？

不可以整除的情况:n＝15，length＝4
(⌈n/length⌉)＝4
(⌈n/length⌉)×length还是4×4＝16啊
整个下标也就到n－1＝14而已
百思不得其解，求解答

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

这个问题涉及到归并排序中的子表划分问题。首先，我们来理解一下归并排序的基本思想。在归并排序中，我们将一个大的数组分成若干个子数组（或称为子表），这些子数组是有序的。然后，我们再将这些有序的数组合并成一个大的有序数组。在这个过程中，我们需要确定每个子数组的起始和结束位置。

对于你的问题，最后一个子表的起始下标为什么是 (⌈n/length⌉)×length，而不是 (⌈n/length⌉-1)×length？

原因在于，我们需要确保每个子表的长度至少为 length。当我们计算 (⌈n/length⌉-1)×length 时，我们可能会漏掉一些元素，因为这些元素不在任何子表中。但是，当我们使用 (⌈n/length⌉)×length 时，我们确保每个子表都完整地包含了 length 个元素（或更少，如果是最后一个子表）。

让我们来看几个例子：

1. 当 n=16 且 length=4 时： 我们确实有 ⌈16/4⌉=4 个子表。每个子表的长度都是 4，所以最后一个子表的起始下标是 4×4=16，这是正确的。

2. 当 n=15 且 length=4 时： 虽然我们不能整除，但我们仍然有 ⌈15/4⌉=4 个子表。前三个子表的长度接近 4，但最后一个子表的长度可能小于 4。然而，使用 (⌈n/length⌉)×length 可以确保我们考虑到所有元素，即使最后一个子表的长度小于 length。在这种情况下，(⌈n/length⌉)×length 仍然是 4×4=16，但是我们只使用到数组的索引 14（因为总共有 15 个元素）。

现在考虑你的疑问中关于不可整除的情况。在这种情况下，(⌈n/length⌉)×length 可能大于 n。但实际上，我们只需要关心到索引 n-1，因为我们是从索引 0 到 n-1 的数组进行排序。所以，(⌈n/length⌉)×length 只是告诉我们最后一个子表应该从哪里开始考虑划分，而实际的最后一个子表的结束位置会是 n-1 或更小（取决于余数）。因此，(⌈n/length⌉)×length 是为了确保我们考虑到所有元素，即使最后一个子表的长度可能小于 length。