Compare ordering of two lists

Is there an algorithm better than O(n^2) for re-ordering List开发者_运维问答 2 to match List 1

List 1 : A B C D

List 2 : B D C A

note: List 2 can have more, less or even completely different items compared to List 1.

If you can create a total-ordering for the type of items in the lists, then you can create an index for list 1 by sorting the items. You can then use this index to re-order list 2. This algorithm is O(n log n) in time, and requires an extra O(n) in space.

One possibility that would result in O(n Log(n)) would be the following. This requires reading the list values into an array/vector/sortable type of structure:

• Sort list 1 based on value and keep the position information. This provides a quick way to look up an item and know its position. The cost for the sort is O(n log n)
• Sort list 2 using the sorted list from the first step as the compare function. Two compare two values, look them up in the sorted list 1 results and use the relative positions as the comparison between the two values. The cost of this sort is also O(n log n).

After the edit, you mention that the second list may have no correlation to the first list. So the comparison function would have to take that into account. If one or both values being compared are not in the first list, then the compare function needs to make a decision on ordering the values (e.g., do they go at the end or the beginning?).