Merging two small sequencies - algorithm

Question

Prove that it is enough to make at most 5 comparisons in order to merge two sorted sequences of lengths 2 and 5.

Answer 1

Suppose the input arrays are [a b c d e] and [x y]

We start by trying to insert x into the larger array. We do binary search but we take a chance: We don't start in the middle but slightly to the left: We check x < b.

• If we're lucky x falls in the left (smaller) part of the array and we can compare x < a to figure out if the result should start with x a or a x. We then have 3 comparisons left for y which is sufficient to do a binary search.

• If we're unlucky x falls in the right (larger) part of the array. In other words x should be in c d e. We continue the binary search by checking x < d.

  • If we're lucky this is false, because we then know that the result starts with a b c d and we can then check x < e and y < e to figure out the order of the last three elements.

  • If this is true, we check x < c to figure out if the sequence should start with a b c x or a b x. We then have 2 comparisons left which is enough to do a binary search for y since we know that it should be to the right of x.

This is of course just an outline of a solution and not a formal proof. However, it can easily be transformed to a formal proof using Hoare logic. It would look as follows:

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