Question

(Subject: Data Structures and Algorithms)

Faster merging.

You are given two sorted sequences of $\lg{n}$ and $n-1$ keys. We would like to merge those two sorted sequences by performing $o(n)$ comparisons.

(Note we are interested in comparisons, not running time.) Show how this can be done or argue that it cannot be done.

Note: In class we showed that ordinary merging would require no more than $\lg{n}+n-1+1= n + \lg{n}$ comparisons.

Answer 1

Firstly we have given two sorted arrays of lg(n) and n-1 keys that is elements . Here as log is not specified so I am taking lg as logarithm of base 10.
So these are the elements of the given sorted arrays and number of comparisons to be done is merging two sorted arrays are defined by the number of elements of arrays to be merged.
When two sorted arrays are going to be merged the comparisons to be made either in case of worst situation and normal situation is--
Let's consider two sorted list of n and m elements then,

• 1)In case of normal situation it is considered that one array list is small than the other and after comparing all the elements of the smaller list the remaining elements of the other list will be added directly to the new merged array list and the number of comparisons will depend on the smaller array list that is total number of comparisons will be same as number of elements in the smaller list. Let the smaller list have n elements then the number of comparisons to be done will be n that is comparisons will be min(n,m).
• 2)Second case scenario will be when both list have same number of elements then the merged list will be obtained by comparing each list element with the other again and again till the both list are ended. That is in this case the number of comparisons made will be m+n-1.

=========================================================================

Now, lets come to the question.
Let's take n as 10 so in first sorted array number of elements will be lg(10)=1 and in case of second array it will be 9 now it is given that the sorted arrays are merged by having O(n) comparisons but the number of elements we obtained are 1 and 9 that is they are similar to the first case and thus number of comparisons made for n=10 is 1 .
If we take n=100 then the elements will be 2 and 99 still it follows the first case and the number of comparisons made will be 2. There is no situation to be thought of that can have O(n) comparisons.
Thus it cannot be done as the keys given will never generate a situation where the elements will have same elements, the elements of one list will always be smaller than the other list and it will always be smaller than n. Thus it cannot be done.