Question

You are given 2 sorted sequences of log(n) and n-1 keys. We would like to merge those 2 sorted sequences by performing o(n) comparisons.[Note that we are interested in the comparisons and not the running time.]

Show how this can be done or argue how this cannot be done.

In class we show that ordinary merging would require no more than lg(n)+n-1+1 = n+lg(n) comparisons.

Answer 1

If you have two sorted sequences of log(n) and (n-1) keys, merging those two sequences canbe performed with O(n) comparisons. Let's take an example to understand it.

Let's say the value of n = 100. So, log(n) with base 10 = log(100) = 10.
Also, n-1 = 100-1 = 99.

Now, let's say the two sequences are -

seq 1 = [ 100, 101, 102, 103, 104, 105, 106, 107, 108, 109 ] . Size is log(100) = 10.

seq 2 = [1, 2, 3, .... , 99]. Size is n-1 = 99.

We can see that, the number of comparisons that would require will be 99 in this case. This is the worst case scenario and for larger value of N, O(N-1) ~ O(N).

In the above example, in each iteration, 100 is compared with all the elements in seq 2 and since 100 is less than all the elements in seq 2, so everytime the elements of the seq 2 is being inserted in the final sorted sequence. After all the values 1 ... 99 are inserted, the seq 1 elements are then inserted that would require no more comparisons as by now the seq 2 is empty.