Linq sort with a twist

Question

I have the following records

The last 2 are children of record 3 and 4, I would like to be able to sort the records by amount but it should be that the non interest(parents) ones are sorted first then their children should show up after so for example it would be like this

2000
2000
20001
99.84 (child of the above)
50000
249.58 (child of the above)

Basically I would like my sort by amount to disregard the one with "IsInterest" set to true but make them show up after their parent.

I can do this by first taking all the parents into a new collection.. then go through the parent to see if there is any children then insert them after the parent in the new collection but I feel this is not efficient and dirty code so I thought I would ask maybe someone knows black magic. The sort should also be aware of asc/desc on the amount.

I can post my code of ripping the collection apart and putting it together if it helps but I am trying not to use that code if possible.

My sort method takes a string for "ascending" or "descending" if that helps

Thank you

UPDATE2 I will point out that there is only ever going to be 2 levels, and that the children will ever only have one parent (no grand parents) and that each parent will have a maximum of 1 child

UPDATE code as requested (fields name may differ from the db fields..)

 switch (sortMember.ToUpper())
            {
                case "AMOUNT":
                    {
                        //check to see if any imputed interests exist
                        if (contributions.Any(x => x.IsImputedInterest))
                        {
                            var children = contributions.Where(x => x.IsImputedInterest);
                            var sortedColl = contributions.Where(x => x.IsImputedInterest == false).OrderByWithDirection(x => x.ContributionAmount, sortDirection.ToUpper() == "DESCENDING").ToList();
                            foreach (var child  in children )
                            {
                                //find the parent
                                var parentIndex = sortedColl.FindIndex(x => x.ContributionId == child.ParentContirbutionId);
                                sortedColl.Insert(parentIndex+1, child);

                            }

                        }
                        else
                        {
                            contributions = contributions.OrderByWithDirection(x => x.ContributionAmount, sortDirection.ToUpper() == "DESCENDING");
                        }

                        break;
                    }
            }

.................

 public static IOrderedEnumerable<TSource> OrderByWithDirection<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, bool descending)
    {
        return descending ? source.OrderByDescending(keySelector)
                          : source.OrderBy(keySelector);
    }

    public static IOrderedQueryable<TSource> OrderByWithDirection<TSource, TKey>(this IQueryable<TSource> source, Expression<Func<TSource, TKey>> keySelector, bool descending)
    {
        return descending ? source.OrderByDescending(keySelector)
                          : source.OrderBy(keySelector);
    }

Answer 1

You can use the following generic method (not limited by levels or number of parent/children):

public static class Extensions
{
    public static IEnumerable<T> ThenByHierarchy<T, TKey>(this IOrderedEnumerable<T> source, Func<T, TKey> keySelector, Func<T, TKey> parentKeySelector)
    {
        var itemByKey = source.ToDictionary(keySelector);
        var processSet = new HashSet<T>();
        var stack = new Stack<T>();
        foreach (var item in itemByKey.Values)
        {
            for (var next = item; processSet.Add(next); )
            {
                stack.Push(next);
                if (!itemByKey.TryGetValue(parentKeySelector(next), out next)) break;
            }
            while (stack.Count != 0)
                yield return stack.Pop();
        }
    }
}

Just append it at the end of your OrderBy sequence like this

var result = contributions
    .OrderByWithDirection(x => x.ContributionAmount, sortDirection.ToUpper() == "DESCENDING")
    .ThenByHierarchy(x => x.ContributionId, x => x.ParentContirbutionId);

UPDATE: It turns out that it's not so simple. While the method above provides a correct order for the leaf elements as well for the element to its parent, it does not order correctly the parents. The correct one is as follows (using another reusable method from here How to flatten tree via LINQ?, so if we don't count that it isn't really much bigger than the previous):

public static class Extensions
{
    public static IEnumerable<T> HierarchicalOrder<T, TKey>(this IEnumerable<T> source, Func<T, TKey> keySelector, Func<T, TKey> parentKeySelector, Func<IEnumerable<T>, IOrderedEnumerable<T>> order)
    {
        // Collect parent/child relation info
        var itemById = source.ToDictionary(keySelector);
        var childListById = new Dictionary<TKey, List<T>>();
        var rootList = new List<T>();
        foreach (var item in itemById.Values)
        {
            var parentKey = parentKeySelector(item);
            List<T> childList;
            if (parentKey == null || !itemById.ContainsKey(parentKey))
                childList = rootList;
            else if (!childListById.TryGetValue(parentKey, out childList))
                childListById.Add(parentKey, childList = new List<T>());
            childList.Add(item);
        }
        // Traverse the tree using in-order DFT and applying the sort on each sublist
        return order(rootList).Expand(item =>
        {
            List<T> childList;
            return childListById.TryGetValue(keySelector(item), out childList) ? order(childList) : null;
        });
    }
    public static IEnumerable<T> Expand<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
    {
        var stack = new Stack<IEnumerator<T>>();
        var e = source.GetEnumerator();
        try
        {
            while (true)
            {
                while (e.MoveNext())
                {
                    var item = e.Current;
                    yield return item;
                    var elements = elementSelector(item);
                    if (elements == null) continue;
                    stack.Push(e);
                    e = elements.GetEnumerator();
                }
                if (stack.Count == 0) break;
                e.Dispose();
                e = stack.Pop();
            }
        }
        finally
        {
            e.Dispose();
            while (stack.Count != 0) stack.Pop().Dispose();
        }
    }
}

and the usage in your case is simple

var result = contributions
    .HierarchicalOrder(x => x.ContributionId, x => x.ParentContirbutionId, c =>
    .OrderByWithDirection(x => x.ContributionAmount, sortDirection.ToUpper() == "DESCENDING"));

Answer 2

Here's a single statement Linq solution:

var desc = order == "descending";
var result = list
    //group parents with it's children
    .GroupBy(x => x.ParentId ?? x.Id)
    //move the parent to the first position in each group
    .Select(g => g.OrderBy(x => x.ParentId.HasValue).ThenBy(x => desc ? -x.Amount : x.Amount))
    //sort the groups by parents' amounts
    .OrderBy(g => desc ? -g.First().Amount : g.First().Amount)
    //retrieve the items from each group
    .SelectMany(g => g);

Some performance hints:

• You can drop the ThenBy(...) if there's always going to be at most one child or you don't care about children order
• Use an if statement to check the order and have two versions of the statement - the second one using OrderByDescending/ThenByDescending, and drop the ternary operator (desc ? ... : ...) - otherwise it will be evaluated for each item

I'm not giving any guarantees on performance in relation to your current solution - it might as well turn out to be slower.