merge - 合并两个小序列 - 算法

Question

证明最多进行 5 次比较就足以合并两个长度为 2 和 5 的排序序列。

Answer 1

假设输入数组是[a b c d e]和[x y]

我们首先尝试插入x更大的数组。我们进行二分搜索，但我们冒险：我们不是从中间开始，而是稍微向左：我们检查x < b.

• 如果我们幸运地 x落在数组的左侧（较小）部分，我们可以比较x < a以确定结果是否应该以x aor开头a x。然后我们剩下 3 个比较y，足以进行二分搜索。

• 如果我们不走运 x，则落在数组的右侧（较大）部分。换句话说x应该在c d e. 我们通过检查继续二进制搜索x < d。

  • 如果幸运的话，这是错误的，因为我们知道结果以开头，a b c d然后我们可以检查x < e并y < e找出最后三个元素的顺序。

  • 如果这是真的，我们检查x < c以确定序列是否应该以a b c xor开头a b x。然后我们剩下 2 个比较，这足以进行二进制搜索，y因为我们知道它应该在x.

这当然只是一个解决方案的大纲，而不是正式的证明。然而，它可以很容易地转换为使用 Hoare 逻辑的形式证明。它看起来如下：

{ a ≤ b ≤ c ≤ d ≤ e ∧ x ≤ y }
if (x < b) {
    { a ≤ b ≤ c ≤ d ≤ e ∧ x ≤ y ∧ x < b }
    if (x < a) {
        ...
    } else {
        ...
    }
} else {
    { a ≤ b ≤ c ≤ d ≤ e ∧ x ≤ y ∧ b ≤ x }
    if (x < d) {
        ...
    } else {
        ...
    }
}