Hi,

I would like to open a discussion about techniques to merge two sorted lists of words. So the example is as follows:

Code:
A             B

aabax       aaaaax
aabbx       abbbbx
abaax       abaabbx
abbx        baabbx
abx         baax
bbx         babx
the expected result would be

Code:
aaaaax
aabax
aabbx
abaax
abaabbx
abbx
abx
baabbx
baax
babx
bbx
The thing is, we know that to merge two sorted lists we need to take two words from each list and compare them character by character. once a mismatch has been encountered then according to the lexicographic order of the mismatching characters we can decide which one goes first and which goes second.
Code:
aabax
||x
aaaaax

b != a therefore aaaaax < aabax since a is lexicographically smaller then b
Now if the two sets have equal number of characters (n) that means we would need to do O(2n) number of comparisons to merge two sets. Let us assume that we know the longest common prefix of each word(string) in each set. That is, let us assume that we posses knowledge(a priori) that a first word in set A has the longest common prefix = 3, second =3, third =2 ... where longest common prefix is determined only with respect to words in set A and not set B. What would be the cleverest way to merge thees two sets ??

any suggestions ?

thank you

baxy