Sort a list according to order defined by another list

Question

How can I sort the elements of the list A so that they follow the ordering of another (superset) list B? Assume no duplicates.

E.g. A might contain [8 2 5 1] and B might contain [5 6 9 8 7 4 1 2 3], and so I'd like to sort A to become [5 8 1 2]

I'm interested in ways of doing this efficiently and with good runtime complexity.

Answer 1

If B is a superset of A, I'd just dump A into a hash-table, scan B and create a new list where I insert every element from B that is contained in the hash-table. Uses O(a) extra memory and O(b) runtime.

Answer 2

Here are some ideas:

(In the time complexities given, n is the size of A and m is the size of B. The time complexities are not simplified.)

• For each element in B, do a linear search of A to see if that element exists in it. If so, swap it with the first element in A that hasn't yet been put into position. Time complexity: O(nm)
• Same as above, but first put the contents of A into an efficient lookup structure to avoid the linear search. Time complexity: O(n + m) assuming O(1) lookup
• Sort B. Then, for each element in A, find its index (which is guaranteed to exist) within B using binary search. Record this index in an auxiliary array the same size as A. Use that array of indices as input to a comparator that sorts A. Time complexity: O((m log m) + (n log n) + (n log n))