合并两个小序列 - 算法

Question

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

Answer 1

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

我们首先尝试将 x 插入到更大的数组中。我们进行二分查找，但我们抓住机会：我们不是从中间开始，而是稍微向左：我们检查 x < b.

如果我们幸运 x 落在数组的左侧（较小）部分，我们可以比较 x < a确定结果应该以 x a 还是 a x 开头。然后我们为 y 剩下 3 次比较，这足以进行二进制搜索。
如果我们不幸 x 落在数组的右侧（较大）部分。换句话说 x 应该在 c d e 中。我们通过检查 x < d.
继续二进制搜索
- 如果我们幸运这是错误的，因为我们知道结果以 a b c d 开头，然后我们可以检查 x < e 和 y < e 来计算最后三个元素的顺序。
- 如果这是真的，我们检查 x < c 以确定序列是否应以 a b c x 或 a b x 开头。然后我们还有 2 次比较，这足以对 y 进行二进制搜索，因为我们知道它应该在 x.

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

{ 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 {
        ...
    }
}

合并两个小序列 - 算法

Merging two small sequencies - algorithm

merge

proof

array-algorithms