How to optimize LINQ OrderBy if the keySelector is slow?
===

I want to sort a list of objects using a value that can take some time to compute. For now I have code like this:

    public IEnumerable<Foo> SortFoo(IEnumerable<Foo> original)
    {
        return foos.OrderByDescending(foo => CalculateBar(foo));
    }
    
    private int CalculateBar(Foo foo)
    {
        //some slow process here
    }

The problem with the above code is that it will call calculate the value several times for each item, which is not good. The possible optimization is to use cached value (maybe a dictionary), but it will mean that SortFoo will have to clear the cache after each sorting (to avoid memory leak, and I do want the value to be recalculated on each `SortFoo` call).

Is there a cleaner and more elegant solution to this problem? 