为什么要在合并排序中将数组划分为一个元素

Question

我正在读合并排序算法。我有个问题

假设我们有一个列表

列表=5 4 1 3 6 8 9 7

首先将列表划分为4 -4个元素。我们称左侧列表和右侧列表为

5 4 1 3 and 6 8 9 7

然后将5 4 1 3分成以下几部分

5 4 and 1 3

然后将5和4除以

5 4

当排序时，我们将从最后一步开始排序，并继续到步骤1(我们有4-4个元素)

问:不管怎样，当我们将列表划分为1-1个元素，并且我们随时对列表进行排序和合并时，为什么不将列表划分为4-4个元素呢？因为在这种情况下，我们也将进行列表的合并。为什么要迭代到1-1个元素

Answer 1

1元素列表是自然排序的。我们先合并两个1元素排序列表得到2元素排序列表，然后再合并2元素排序列表得到4元素排序列表，依此类推。

Merge过程用于已排序的列表，因此我们不能将merge应用于未排序的5 4 1 3和6 8 9 7列表

Answer 2

从理论上讲，这是因为合并过程需要接受两个排序列表。包含4个元素的列表不会排序，而只有1个元素的列表会排序。

在实践中，我们不会将列表拆分成一个元素。因为合并排序不是小列表的最有效排序算法，所以插入排序是最有效的排序算法。因此，常用的优化方法是使用插入排序对小列表进行排序，然后将它们与合并排序合并。

Answer 3

因为如果您使用合并排序的方式进行排序，则存在一个不变量，该不变量表示合并列表(拆分后)是排序的，这意味着在合并拆分列表之后的每个级别上，合并列表都是排序的。

例如，如果您在拆分成4-4之后立即合并，将比较两个列表的第一个项目，而这两个值可能都不是那些拆分的列表中的最小值，这意味着您最终得到的结果列表的排序很可能没有排序。