合并排序初学者问题

我现在有一个关于归并排序算法的问题。因为在原始算法中，将要排序的列表分为两个子列表并递归排序。 现在我想将长度为 n 的列表分为 3 个长度为 n/3 的子列表，然后对这三个子列表进行递归排序，然后合并，怎么样？ 我只是简单地修改了原始算法，将所有地方的 2 替换为 3，想知道这是否有意义。

让它更通用怎么样？我们可以将列表分成K个子列表，然后对它们进行排序并组合吗？

感谢您与我分享您的想法。

如果您有 n (n > 2) 个列表，则不需要在每个合并步骤上执行 (n-1) 次比较。然而，实现变得更加复杂。

假设你有三个列表，list[0..2]，并假设为简单起见，您正在合并它们，并且它们仍然非空（即您还没有运行到任何列表的末尾）。为了简单起见，进一步假设所有元素都是不同的，即当您比较两个元素时它们永远不会相同。然后，您有六种可能的“状态”，它们对应于三个列表的六种排列，按列表中第一个元素的递增顺序排列，即，如果

list[0] = [5, 7, 11, 15]
list[1] = [3, 4, 20, 21]
list[2] = [9, 10, 12, 19]

那么列表对应的排列是[1,0,2]，即list[1]具有最少的前部元素并且list[2]具有最大的前部元件。

当您现在弹出下一个元素 (4) 时list[1]你已经知道了list[0].front < list[2].front基于您所在的状态 [1, 0, 2]。所以现在您需要执行 1 或 2 次比较：

if (list[1].front < list[0].front) // (A)
   --> move to state [1, 0, 2], next to pop is list[1]
else if (list[1].front < list[2].front)
   --> move to state[0, 1, 2], next to pop is list[0]
else
   --> move state[0, 2, 1], next to pop is list[0]

假设某种均匀性，比较 (A) 返回 true 的概率为 1/3，即删除前一个元素的列表中的下一个元素小于其他两个列表中的最小元素，因此平均而言，您有 (1/3 x 1 + 2/3 x 2) = 5/3 次比较，而不是 2 次（这将是 n-1）。

这显然更糟糕，每次插入需要 2/3 次比较，而普通合并排序只需要每个弹出元素进行 1 次比较。

通过考虑部分有序状态，我们可以获得更好的结果。可以进行三种不同的比较（list[0] -- list[1]、list[1] -- list[2] 和 list[0] -- list[2]）。如果我们允许用“不知道”（？）来增强已知结果（），则有以下可能的状态：

0/1  1/2  0/2
  <    <    <   (total order) [0,1,2]
  <    ?    <   (0 is least but don't know if 1 < 2) [0,1,2] [0,2,1]
  <    ?    ?   (0 is < 1, but 2 can't be positioned) [2,0,1] [0,2,1] [0,1,2]
  ?    ?    ?   (no information about ordering) (all six permutations)

然后是关于排列和在矩阵中不同位置交换 的所有变体。

现在，如果处于 (

现在在 (

为了完整起见，这里是算法（显示片段）：

state_1_lt_2: /* known list[1].front < list[2].front */
  if (list[0].front < list[1].front):
    merge_from(0)
    goto state_1_lt_2 /* 1 insert 1 comp prob 1/3 */
  else
    merge_from(1)
    if (list[0].front < list[1].front)
      if (list[1].front < list[2].front)
        merge_from(0)
        goto state_1_lt_2 /* 2 inserts 3 comps prob 2/3*1/2*1/3 = 1/9 */
      else if (list[0].front < list[2].front)
        merge_from(0)
        goto state_2_lt_1 /* 2 inserts 4 comps prob 2/3*1/2*2/3*1/2 = 1/9 */
      else
        merge_from(2)
        goto state_0_lt_1 /* 2 inserts 4 comps prob 1/9 */
    else if (list[2].front < list[1].front)
      merge_from(2)
      goto state_1_lt_0 /* 2 inserts 3 comps 2/3 x 1/2 x 1/3 = 1/9 */
    else if (list[2].front < list[0].front)
      merge_from(1)
      goto state_2_lt_0 /* 2 inserts 4 comps prob 1/9 */
    else
      merge_from(1)
      goto state_0_lt_2 /* 2 inserts 4 comps prob 1/9 */

这总计为每次插入的预期比较次数

1/3 x 1 + 4/9 x (4/2) + 2/9 x (3/2) = 6/18 + 16/18 + 6/18 = 30/18 = 1 5/9.