using System;

using System.Linq;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        var admin = 1;

        var rep = 2;

        var dealer = 3;

        var objects = new MyObject[]{

            // another top level message by admin should get grouped into his prevoius message

            new MyObject() { Id = 9, SentBy = admin, InReplyTo = null, Level = 0, ShouldBe = 0, Message = "top level message #1" },

            new MyObject() { Id = 10, SentBy = dealer, InReplyTo = 9, Level = 1, ShouldBe = 1, Message = "reply to top level message #1" },

            new MyObject() { Id = 5, SentBy = admin, InReplyTo = null, Level = 0, ShouldBe = 2, Message = "top level message #2 (REPLY UNDER top level #1)" }, // this one should become a reply

            new MyObject() { Id = 6, SentBy = dealer, InReplyTo = 5, Level = 1, ShouldBe = 3, Message = "reply to top level message #2" },

            new MyObject() { Id = 8, SentBy = dealer, InReplyTo = 5, Level = 1, ShouldBe = 4, Message = "reply 2 to top level message #2" },

            new MyObject() { Id = 1, SentBy = admin, InReplyTo = null, Level = 0, ShouldBe = 5, Message = "top level message #4 (REPLY UNDER top level #1)" },

            new MyObject() { Id = 3, SentBy = dealer, InReplyTo = 1, Level = 1, ShouldBe = 6, Message = "reply to top level message #4" },

            new MyObject() { Id = 2, SentBy = rep, InReplyTo = null, Level = 0, ShouldBe = 7, Message = "top level message #3" },

            new MyObject() { Id = 4, SentBy = dealer, InReplyTo = 2, Level = 1, ShouldBe = 8, Message = "reply to top level message #3" },

            new MyObject() { Id = 7, SentBy = dealer, InReplyTo = 2, Level = 1, ShouldBe = 9, Message = "reply 2 to top level message #3" },

        };

        // order them:

        //var sorted = new List<MyObject>();

        //var topLevel = new List<MyObject>();

        //var topLevelTemp = objects.Where(o => o.Level == 0).OrderByDescending(o => o.Id).ToList();

        //var replies = objects.Where(o => o.Level == 1).ToList();

​

        // top level: figure out the true top levels (as we'll combine top-level messages sent by the same user into the replies)

        //foreach (var topLevelMessage in topLevelTemp) {

        //  if (topLevel.Any(o => o.SentBy == topLevelMessage.SentBy)) {

        //      replies.Add(topLevelMessage);

        //      continue;

        //  }

        //  topLevel.Add(topLevelMessage);

        //}

        // replies:

        //foreach(var topLevelMessage in topLevel) {

        //  sorted.Add(topLevelMessage);

            // replies to this top level message (order by asc)

        //  var repliesToThisMsg = replies.Where(o => o.InReplyTo == topLevelMessage.Id).ToArray();

        //  foreach(var replyToThisTopLevelMsg in repliesToThisMsg) {

        //      sorted.Add(replyToThisTopLevelMsg);

        //  }

            // additional top level messages (order by desc)

        //  foreach(var additionalTopLevelMsg in replies.Where(o => o.Level == 0 && o.SentBy == topLevelMessage.SentBy)) {

        //      sorted.Add(additionalTopLevelMsg);

        //      foreach(var replyToAdditionalTopMsg in replies.Where(o => o.InReplyTo == additionalTopLevelMsg.Id)) {

        //          sorted.Add(replyToAdditionalTopMsg);

        //      }

        //  }

        //}

        // print them:

        //for(var i = 0; i < sorted.Count; i++) {

        //  if (sorted[i].ShouldBe == i) {

        //      Console.WriteLine("SUCCESS: " + i + "; Message: " + sorted[i].Message);

        //  } else {

        //      Console.WriteLine("ERROR: " + i + "; Message: " + sorted[i].Message);

        //  }

        //}

        // -----------------

        var threads = (from m in objects

                       let replies = objects.Where(o => o.InReplyTo == m.Id).OrderBy(o => o.Id)

                       where m.Level == 0

                       orderby m.Id descending

                      select new {

                          TopMessage = m,

                          Replies = replies

                      }).ToArray();

        var groups = from thread in threads

                     group thread by thread.TopMessage.SentBy into g

                     orderby g.First().TopMessage.Id descending

                     select g;

        var sorted = groups.SelectMany(g => g.ToArray());

        foreach(var item in sorted) {

            Console.WriteLine(item.TopMessage.ShouldBe);

            foreach(var subitem in item.Replies) {

                Console.WriteLine(subitem.ShouldBe);    

            }

        }

    }

}

​

public class MyObject {

    public int Id { get; set;}

    public int SentBy {get;set;}

    public int? InReplyTo {get;set;}

    public int Level {get;set;}

    public int ShouldBe {get;set;}

    public string Message {get;set;}

}