How can we use LINQ to sort a list where some predefined values should appear first?

Question

Similar to this Java question I want to sort a List<T> where a known set of values should come first (if present), after which we use the default order - e.g. EqualityComparer<T>.Default. Efficient code is desirable, but I'm more interested in a clever LINQ expression.

Sample data

Known:    e c
Input:    c b e d a
Output:   e c a b d

Known:    e c
Input:    b a c e c
Output:   e c c a b

Known:    e c
Input:    b d f a
Output:   a b d f

Wanted API

Some minor tweaks might be necessary. Note the keySelector, allowing us to choose a property as sorting target.

public static class EnumerableExtensions
{
    public static IEnumerable<TSource> Sort<TSource, TKey>(
        this IEnumerable<TSource> input,
        Func<TSource, TKey> keySelector, TKey[] knownValues)
    {
        // TODO: Clever LINQ implementation here!
        yield break;
    }
}

Sample program

class Program
{
    public class Foo
    {
        public Foo(string name) => Name = name;
        public string Name { get; }
        public override string ToString() => Name;
    }

    public static void Main()
    {
        string[] knownValues = { "e", "c" }; // We can assume that these values are unique!
        var (a, b, c, d, e) = (new Foo("a"), new Foo("b"), new Foo("c"), new Foo("d"), new Foo("e"));
        
        var input = new List<Foo> { c, b, e, d, a };
        var expected = new List<Foo> { e, c, a, b, d };
        var actual = input.Sort(t => t.Name, knownValues).ToList();
        
        Console.WriteLine(expected.SequenceEqual(actual) ? "SUCCESS" : "FAIL");
        Console.WriteLine("Expected: " + string.Join(", ", expected));
        Console.WriteLine("Actual:   " + string.Join(", ", actual));
    }
}

Answer 1

This should do the trick :

var actual = input
    .OrderByDescending(o => knownValues.Contains(o.Name))
    .ThenBy(o => knownValues.FindIndex(p => o.Name == p))
    .ThenBy(o => o.Name)
    .ToList();

OrderByDescending will split the list in two parts. The known values and the unknown values. The first ThenBy will order the known values in the same order than the knownValues array and the last ThenBy will order the unknown values.

Answer 2

Unfortunately .Net doesn't have an IndexOf that returns one past the upper bound when the element isn't found, but you can write one:

public static class ArrayExt {
    public static int PastIndexOf<T>(this T[] array, T val) {
        var index = array.IndexOf(val);
        return index == -1 ? array.Length : index;
    }
}

NOTE: This feels unfortunate to me, since the framework has special code to handle the -1 return and now we are adding special code on top of it to undo that, but writing our own implementation would probably be slower then Array.IndexOf which has special optimizations.

With this extension method, your method is simple:

public static IEnumerable<TSource> Sort<TSource, TKey>(this IEnumerable<TSource> input, Func<TSource, TKey> keySelector, TKey[] knownValues)
    => input.OrderBy(i => knownValues.PastIndexOf(keySelector(i))).ThenBy(i => keySelector(i));

Alternatively, you can use a generic extension method to catch the concept of testing and replacing a value:

public static class ObjectExt {
    public static T ElseIf<T>(this T a, Func<T,bool> testFn, T b) => testFn(a) ? b : a;
}

And then write your method using this:

public static IEnumerable<TSource> Sort<TSource, TKey>(this IEnumerable<TSource> input, Func<TSource, TKey> keySelector, TKey[] knownValues)
    => input.OrderBy(i => knownValues.IndexOf(keySelector(i)).ElseIf(n => n == -1, knownValues.Length+1)).ThenBy(i => keySelector(i));

NOTE: Of course, these extension methods makeup for C#'s lack of a easy declaration expression where you could just use ?:. These are generalizations of ?? that feel like could use a more succinct expression, but I don't know what it would be.

PS: You can have a declaration expression, it just hard to read:

public static IEnumerable<TSource> Sort<TSource, TKey>(this IEnumerable<TSource> input, Func<TSource, TKey> keySelector, TKey[] knownValues)
    => input.OrderBy(i => (knownValues.IndexOf(keySelector(i)) is var v) && v >= 0 ? v : knownValues.Length+1).ThenBy(i => keySelector(i));

PPS: Or using C# 9 extended pattern matching:

public static IEnumerable<TSource> Sort<TSource, TKey>(this IEnumerable<TSource> input, Func<TSource, TKey> keySelector, TKey[] knownValues)
    => input.OrderBy(i => knownValues.IndexOf(keySelector(i)) is var v and >= 0 ? v : knownValues.Length+1).ThenBy(i => keySelector(i));

PPPS: As pointed out by @l33t, a uint cast of the return value of IndexOf will produce the proper ordering:

public static IEnumerable<TSource> Sort<TSource, TKey>(this IEnumerable<TSource> input, Func<TSource, TKey> keySelector, TKey[] knownValues)
    => input.OrderBy(i => (uint)knownValues.IndexOf(keySelector(i))).ThenBy(i => keySelector(i));
    // cast IndexOf return value to uint to move not found to the end

Answer 3

Yes. The easiest method is probably to use .ThenBy

Example assumes the items are comparable and equatable for simplicity, and that input and knownvalues have the same type.

input.OrderBy(i => knownValues.Contains(i) )
      .ThenBy(i => i)