Sort a list in memory with another list in memory

Question

Can I sort the list in memory with another list (the second list will be a reference data source or something like that)?

public class DataItem
{
    public string Name { get; set; }
    public string Path { get; set; }
}

// a list of Data Items, randomly sorted
List<DataItem> dataItems = GetDataItems();

// the sort order data source with the paths in the correct order
IEnumerable<string> sortOrder = new List<string> {
    "A",
    "A.A1",
    "A.A2",
    "A.B1"
};

// is there a way to tell linq to sort the in-memory list of objects
// by the sortOrder "data source"
dataItems = dataItems.OrderBy(p => p.Path == sortOrder).ToList();

Answer 1

First, let's assign an index to each element in sortOrder:

var sortOrderWithIndices = sortOrder.Select((x, i) => new { path = x, index = i });

Then we attach the two lists and sort:

var dataItemsOrdered =
 from d in dataItems
 join x in sortOrderWithIndices on d.Path equals x.path //pull index by path
 orderby x.index //order by index
 select d;

This is how you do it in SQL.

Answer 2

Here is an alternative (and I affirm a more effective) approach to accepted as an answer.

List<DataItem> dataItems = GetDataItems();
IDictionary<string, int> sortOrder = new Dictionary<string, int>()
{
     {"A", int.MaxValue},
     {"A.A1", int.MaxValue-1},
     {"A.A2", int.MaxValue -2},
     {"A.B1", int.MaxValue-3},
};

dataItems.Sort((di1, di2) => sortOrder[di1.Path].CompareTo(sortOrder[di2.Path]));

, Sort() OrderBy() O (n * logn), n - dataItems. O (n * logn) . , , sortOrder, , IEnumerable .

join, , O (nm), m - sortOrder. , O (nm + nlogn).

, join, O (n * (m + logn)) ~ = O (n * logn) . join . , linq, linq.

Answer 3

If your list of paths is long, you'd better do a dictionary search:

var sortValues = sortOrder.Select((p, i) => new { Path = p, Value = i })
                          .ToDictionary(x => x.Path, x => x.Value);

dataItems = dataItems.OrderBy(di => sortValues[di.Path]).ToList();

Answer 4

a custom order is executed using a custom resolver (implementation of the IComparer interface), which is passed as the second argument to the OrderBy method.