Merge Sorted Sublists to Sorted Superlist

Question

I have a List of n sorted Lists with m elements (Strings) each. Those elements originate from a List with a distinct order that I don't know. What I know is that all sublists maintain the element's global order. The lists are not disjoint. The union of the lists is a subset of the original list.

Now, I'm struggling to find an algorithm that would efficiently combine them back into a List (of Lists) with maximum sorting accuracy.

Is there a Solution out there for such a problem?

I am using Java, here is some sample code:

List<List<String>> elements = new ArrayList<>();

elements.add(Lists.newArrayList("A","D","F"));
elements.add(Lists.newArrayList("B","D","E"));
elements.add(Lists.newArrayList("A","B","G"));
elements.add(Lists.newArrayList("C","D","H"));

// the required method
List<List<String>> sorted = sortElements(elements);

/* expeced output:
 * [["A"],["B"],["C"],["D"],["G","F","E","H"]]
 */

Answer 1

You are seeking for topological sorting.

Your initial lists represent directed graph arcs (A->D, D->F etc)

P.S. Special kind of topological sort in order to explicitly divide nodes by levels is called in Russian literature "Demoucron algorithm", but I failed to find proper English description (found links to planar graph drawing articles)

Example of its work: