Mrege sort text equivalent

[nuzzle]

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.

I don't quite agree. I think the complexity is determined by the total number of words, not the number of characters. The complexity will be O(N+M) where N and M are the number of words in A and B respectively.

The number of characters enters the picture only indirectly. The actual runtime of the algorithm will depend on how many characters must be compared on average to establish the order between pairs of words. It will be a data dependent constant which varies with what the words actually look like.

Spontaneously I don't think the longest common prefix alone will be enought to lower the complexity. I think in addition you need to treat consecutive words with the same longest common prefix as groups. Then if an A prefix is enougth to establish the order in relation to a B word the same order holds for all words in that prefix group. It means that sometimes a whole A group can be ordered with just one comparision and that will lower N (and if B words are grouped too that will lower M). But the efficiency of such grouping will depend on the actual words and thus be data dependent so the complexity still is O(N+M).

Finally note that instead of grouping according to the longest common prefix a fullblown prefix tree can be used. The A list (and optionally the B list too) would be turned into a prefix tree where each node holds the common prefix of all its subnodes. When the order of an A tree node in relation to a B word is established the order of all subnodes (and the words they represent) is known to be the same. A prefix tree represents a more sophisticated grouping if you will (but not necessarily more efficient).