November 8th, 2012, 09:25 AM
Mrege sort text equivalent
I would like to open a discussion about techniques to merge two sorted lists of words. So the example is as follows:
the expected result would be
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.
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 ??
b != a therefore aaaaax < aabax since a is lexicographically smaller then b
any suggestions ?
Click Here to Expand Forum to Full Width