Sort by typical position?
As I understand your question, your problem statement is:


  Given a set of ordered lists $\{L_1,L_2,\ldots,L_n\}$, learn the relation $r(a,b)$ for the partial order of each $L_1,L_2,\ldots,L_n$. Then use this learned relation to sort a new list.


So, in your example, the relation would be the lexicographical order. But your data set has some noise because the last list breaks the order in several places.

This seems to be a case of preferrence learning, and more specifically, object ranking.