# $k$-way merge but without an absolute order

I have $k$ lists that I would like to combine to a single list. Each list's elements are unique and are sorted in a particular order, but there is no notion of an absolute order, and different items across lists can only be compared if they are equal. To give a specific example (here I use $<$ to indicate the sorting inside each list):

l1 = a < b < c
l2 = b < d


l1 + l2 should result in one of the following (and I don't care which one it results in):

a < b < c < d
a < b < d < c


If the lists are incompatible, e.g. a < b and b < a then I want to get an error. The resulting list (if it exists) should respect all of the orderings of the sublists. Also all the items should be unique in the result.

I thought about modifying k-way merge somehow but it's not clear to me how to do that without a global order. By the way, I'll probably be happy with a $O(nk)$ solution.

Perhaps a better way to phrase the problem is this. I'd like to construct an order vector given $k$ pieces of that order vector (or get an error if that's impossible).

Here's an algorithm that I think works for $k=2$. Find and mark all the duplicates - I think this is $O(n)$ - then start writing down elements from first list until you hit a duplicate, once you do add all elements from second list until you hit that same duplicate, then write down the duplicate and continue. The part where it's a bit more tricky with $k>2$ is that the duplicate may not be in every list to do the above (and this process cannot be done sequentially, i.e. l1+l2+l3 is generally not the same as (l1+l2)+l3, where + denotes this operation of finding the superset order list).

It should be easy to extend the above to any $k$. Use a hash to find which lists each unique element belongs to. Then traverse along the first list using the above logic - writing down all elements until you hit first duplicate, in which case write down all elements (that haven't been written down yet) in all other lists before that duplicate and keep doing that until you reach the end of first list. If haven't reached the end of second list, continue same algorithm there and so on. Each list will be traversed twice - once to get the duplicates, and second time to do the above, making it $O(n)$. A compatibility error will be discovered if you iterate along a list but can't find the duplicate (because it was already written down in an earlier pass).

• I'm not clear on what you mean by "there is no notion of an absolute order". Can you elaborate? Can I assume it'll never happen that you have a < b in l1 but b < a in l2? Also, is the following an accurate characterization of your problem? "There exists a total order or partial order on all of the items, and each list happens to be sorted order (according to this total/partial order), but we have no way to query this partial/total order -- all we can do is compare two items to see whether they are equal." Is that what you had in mind? The question is not entirely clear. – D.W. Oct 24 '13 at 22:43
• Also, what is $n$, in your notation? You mean an $O(nk)$ solution would be acceptable: is $n$ the number of items in each of the $k$ sublists, or is it the total number of items across all sublists, or is it the number of items in the combined list? – D.W. Oct 24 '13 at 22:45
• if it so happens that l1 has a<b and l2 has b<a I want to get an error as output. $n$ is total number of items. I think you got the problem @DW. I really thought I had an $O(n logn)$ solution for k=2 (or maybe even $O(n)$) - I'll add more info a bit later. – eddi Oct 25 '13 at 12:45
• eddi, your algorithm for $k=2$ is exactly the algorithm that I proposed earlier in my original answer (I proposed an answer for general $k$, but if you specialize my algorithm to $k=2$, we get the algorithm you described). My original answer generalizes to arbitrary $k$. However, it looks like your edits have significantly changed the constraints on the algorithm. You mean you can hash items? Awesome! Earlier, you said that all we can do is compare two items for equality -- the ability to hash items is very powerful and allows much better algorithms. I've edited my answer to reflect this. – D.W. Oct 25 '13 at 18:35

Edit: You recently revised the question to clarify that you are allowed to hash items. That changes the question: it lets us build much more efficient algorithms.

With this change, your question becomes: given $k$ partial orders, find a total order that is consistent with all of the $k$ partial orders. This problem can be solved in linear time, i.e., in $O(n)$ time, where $n$ is the total number of items across all of the sublists.

Here's how to solve it. We'll build a directed graph, where each item (in any sublist) is a vertex is the graph. Traverse the sublists to extract all consecutive pairs of items that appear in any sublist. If you have a < b in a sublist (i.e., item a immediately precedes b in some sublist), add an edge $a \to b$ to the graph. (Notice that you can have a hashtable that maps the item a to the corresponding vertex $a$ in the graph, so this operation involves two lookups in the hashtable and then adding an edge: $O(1)$ time.)

Once you've built the entire graph, topologically sort it, and output the vertices in topologically sorted order. That will be a valid output list that solves your problem. If the topological sort fails and reports that the graph has a cycle, then your sublists are inconsistent and you should output an error.

This solves your problem in linear time, i.e., $O(n)$ time.

My original answer to your original question: You don't list any requirements on what order the combined list elements must appear in. Therefore, concatenating/interleaving all of the list items in an arbitrary order appears to meet all of the explicitly stated requirements. If that's not an acceptable solution, you'll need to think through your requirements more carefully and then edit your question to state the requirements explicitly.

I suspect you meant to require that the elements in the combined list must appear in an order that is consistent with the order in each sublist, and any item should appear only once in the combined list. If that's what you meant, then you can't do better than $O(n^2)$ time, where $n$ is the total number of items across all of the sublists: there's no way to avoid comparing each item of each sublist with each other. (If there is any pair of items which you have not compared explicitly, you have no way of knowing whether they are equal or not: both are possible.)

It's easy to achieve an $O(n^2)$-time algorithm. You simply compare each item to all other items, to first find all duplicated items (items that appear in more than one sublist). Then, you do a straightforward $k$-way merge. At each step of the $k$-way merge, you look at the head of each of the $k$ sublists and classify each of those $k$ items as duplicated or not. If any of them are non-duplicated, you can remove it from the head of its sublist and append it to the combined list. If one of them is duplicated, and all of its duplicates appear among these $k$ items, then you remove each of them from their corresponding sublists and append it to the combined list. Repeat this until done. If no items appears twice in any sublist, and if all of the sublists are sorted in a compatible way (e.g., you don't have a before b in one sublist but b before a in another sublist), then this process will never get stuck and will yield the desired output.

The running time of this algorithm is $O(n^2)$, and it's not possible to do better than that (assuming the only operation available on items is to test two items for equality), so this algorithm is optimal up to a constant factor.

• Thanks, I edited OP. This is great but I don't think you've proven that I can't do better than that, so I'm still hoping for better – eddi Oct 24 '13 at 22:27
• @eddi, I've edited my answer to try to elaborate on why you can't do better, i.e., why you need to compare all items pairwise. I admit that I'm guessing at what your question means -- this is because your question doesn't spell out your requirements very clearly and doesn't specify very clearly what we can and can't assume. Would you like to try a cut at revising your question to be more explicit and precise? – D.W. Oct 24 '13 at 22:42
• @eddi, I've edited my answer to reflect the changes you've made to the question. Given your statement that we're allowed to hash items (not just compare two items for equality), it is now possible to build a much more efficient algorithm -- which I've added to my answer. – D.W. Oct 25 '13 at 18:33
• can you provide a link to topological sorting you mention and its complexity? – eddi Oct 25 '13 at 19:00
• @eddi, do a search, or look in any algorithms textbook. It's a standard topic and a standard algorithm. Running time is linear. – D.W. Oct 25 '13 at 19:28