Question

Suppose we are given two skip lists, one storing a set A of m keys, and the other storing a set B of n keys. Describe and analyze an algorithm to merge these into a single skip list storing the set A ∪ B in O(n + m) expected time. Do not assume that every key in A is smaller than every key in B; the two sets could be arbitrarily intermixed.

Answer 1

Merging two files is using a algorithm like this is, used for merging huge files in our hard disk when the total space exceed the RAM.

Now there are two cases, on is that both A and B are sorted, surely we don't know the relationship between elements together but within A and B the elements are sorted. (If not sort them first using any algorithm)

Now when you have these two, sorted List A and B then what we can do next is merge these in a sequential order

Let's say the files are sorted in descending order let's say the top of the list looks like below

A = 1,2,6,9.....

B = 2,5,8.......

Now while merging we take the first element of both the list, i.e here 1,2 and take comparison choose the smaller one to be placed in C ( final list).

Next since we chose form A next item of A is in so compare 2,2 since both are equal then we enter both, so C = (1,2,2...) and have two more elements i.e 6,5 and move ahead so on.

Once one of the list is empty, in that case the other list is already sorted so we just add it at the end of the list.

Formally we can write this Algorithm as :

Step 1: Take input from both the list, and compare

Try: If (a>b):

insert a in C, and take next value of A in a

Elif (a<b):

insert b in C, and take next value of B in B.

else:

insert a,b in C and take the next value of A,B in a,b

Except:. // When there is no more elements let in either list or both of them.

if ( A.empty()) : put all elements of B in C

. .if(B.empty()): put all elements of A in C

After all this is done the list C will have the merged result of A and B .

Comping to the result complexity, it's clearly visible that we are just going one element at the time to next one and traversing two list of size N,M so it's O(n+m)

It can be written as

T(N+M) = T(N+M-1) + 1

Description as merging two list of M+N Elem is merging lost of M+N-1 and a constant step ( compare and insert).

Hope it helps

The Lanagauge in the Ques has said it can be arbitrarily intermixed.

But if that was the intend you can do it in O(m) time by adding the elements of B at end of A or wise versa but the detailed explaination above make more sense to have a merging of sorted array.

But in case arbitrarily means that some elements of A is small then some elements of B then it's fine our described methods is the most effective way to do it in O(n+m).