What's the best LINQ way to filter a sequence around a pivot?

Question

I'm playing with QuickSort and LINQ, and want to separate the sequence into item before, equal-to, and after a pivot.

Here's what I have so far:

    public static Tuple<IEnumerable<T>, IEnumerable<T>, IEnumerable<T>> ComparativeWhere<T>(this IEnumerable<T> source, T t)
        where T : IComparable<T>
    {
        return new Tuple<IEnumerable<T>, IEnumerable<T>, IEnumerable<T>>(
            source.Where(x => x.CompareTo(t) < 0),
            source.Where(x => x.CompareTo(t) == 0),
            source.Where(x => x.CompareTo(t) > 0)
            );
    }

What's the best way to do this? Is this the best implementation, or is there a better one? Or should I be using a library function I don't know about?

Answer 1

Hey Jay, Wes Dyer's article on this might be helpful to you.

http://blogs.msdn.com/wesdyer/archive/2007/03/01/immutability-purity-and-referential-transparency.aspx

Answer 2

If performance is an issue (and when sorting it usually is, although this is just for fun), I would suggest possibly not using anything built in, because the way you're doing it, is your calling Where 3 times, which causes the enumerable to be iterated 3 times. I would just do this:

public static Tuple<IEnumerable<T>, IEnumerable<T>, IEnumerable<T>> ComparativeWhere<T>(this IEnumerable<T> source, T t)
where T : IComparable<T>
{

    var list1 = new List<T>();
    var list2 = new List<T>();
    var list3 = new List<T>();

    foreach (var item in source)
    {
        if (item.CompareTo(t) < 0)
        {
            list1.Add(item);
        }

        if (item.CompareTo(t) == 0)
        {
            list2.Add(item);
        }

        if (item.CompareTo(t) > 0)
        {
            list3.Add(item);
        }
    }

    return new Tuple<IEnumerable<T>, IEnumerable<T>, IEnumerable<T>>(list1, list2, list3);
}

Of course the two drawbacks with this approach is that you're creating 3 new lists, and it's no longer lazily executed, but everything in life is a trade off isn't it? :)