Sort a List based on a Pre-Sorted List

Question

How can I sort a list based on a pre-sorted list.

I have a list which is already sorted. Say, my sorted list is

{"Junior Developer", "Developer", "Senior Developer", "Project Lead"}

Now, I want to sort any subset of the above list in the same order as the above list. That is, if I have as input

{"Developer", "Junior Developer"}, I want the output as {"Junior Developer", "Developer"}

If the input is {"Project Lead", "Junior Developer", "Developer"}, I want the output as

{"Junior Developer", "Developer", "Project Lead"}. 

How can I achieve the same?

Answer 1

The simplest way would be to use LINQ's .OrderBy extension method, along with the IndexOf method (or equivalent) of your pre-sorted collection. The idea here is to sort using a different value as the "sort key" (this is quite useful, since often we'll want to sort objects based on one of their properties).

var sorted = listToSort.OrderBy(s => listPreSorted.IndexOf(s)).ToList();

And here's an example with arrays: http://ideone.com/7oshhZ

---

Note that if your lists are very large, this will likely be slow, since each item in your target list has to be sequentially looked up in your pre-sorted collection (O(N * M), where N is the length of the target list, and M is the length of the pre-sorted list).

To overcome this limitation, you could generate a lookup mapping the items of your pre-sorted list to their indices, then use this lookup in your .OrderBy (this would have a runtime of O(N + M), and you could re-use the lookup if needed):

var preSortedLookup =
        listPreSorted.Select((v, i) => new { Key = v, Value = i })
                     .ToDictionary(kvp => kvp.Key, kvp => kvp.Value);

var sorted = listToSort.OrderBy(s => preSortedLookup[s]).ToList();

Answer 2

If there are no duplicates in either of the two lists then you can simply use Intersect, which will preserve the order:

var allRoles = new[] {"Junior Developer", "Developer",
                      "Senior Developer", "Project Lead"};
var roles = new[] {"Developer", "Junior Developer"};
var sortedRoles = allRoles.Intersect(roles);

That would probably be more efficient than sorting by IndexOf but you're not likely to notice much difference unless the lists are very long.