title: LINQ sort a flat list based on childorder
body: <p>I am currently trying to figure out a good way to sort my elements with LINQ and C#, but I am kinda failing to do so.</p>
  
  <p>For the problem let assume you have the following Table</p>
  
  <pre><code>---TempTable
  ID (int)
  ParentID (int)
  Name (varchar)
  SortOrder (int)
  </code></pre>
  
  <p>The ID and ParentID are related to each other and give me a self hierachical data structure.
  The root elements have a null in the ID Field.
  The SortOrder is only a portion of the whole table and based on the ParentID, so the elements that share the same ParentID do have 1, 2, 3 in it.</p>
  
  <p>Lets further assume the following data:</p>
  
  <pre><code>ID = 1
  ParentID = null
  Name = Test 1
  SortOrder = 1
  
  ID = 2
  ParentID = 1
  Name = Test 2
  SortOrder = 1
  
  ID = 3
  ParentID = 1
  Name = Test 3
  SortOrder = 2
  
  ID = 4
  ParentID = 2
  Name = Test 4
  SortOrder = 1
  </code></pre>
  
  <p>My desired flat list should have the following order:</p>
  
  <pre><code>Test 1 //root element with sort order 1 = very top
  Test 2 //child element of root with sort order 1
  Test 4 //child element of test 2 with sort order 1
  Test 3 //child element of root with sort order 2
  </code></pre>
  
  <p>Also I like to get the object itself without only getting a portion of information threw the usage of select new ...</p>
  
  <p>This is one of my failed tries:</p>
  
  <pre><code>from x in EntityModel.TempTables //DbSet&lt;TempTable&gt; by EntityFramework - which already holds all elements
     orderby x.SortOrder
     from y in x.TempTableChildren //Navigation Property by EntityFramework
     orderby y.SortOrder
     select y
  </code></pre>
  
  <p>Thanks in advance for your help.</p>
  
  <p><strong>Edit:</strong></p>
  
  <p>The order with the ParentID maybe helpfull, with the given TestData since the ID, ParentIDs are in perfect order but this isnt the case in a real live application since its data driven, someone could delete a entry create a new one and place it in a certain order under a parent and you would have something like :</p>
  
  <pre><code>ID = 193475037
  ParentID = 2
  Name = Test 192375937
  SortOrder = 25
  </code></pre>
  
  <p>Now in the application it would be possible to move this one and the ParentID and SortOrder would change randomly to something like:</p>
  
  <pre><code>ID = 193475037
  ParentID = 456798424
  Name = Test 192375937
  SortOrder = 4
  </code></pre>
  
  <p>To furhter explain the problem here is some code - how I would do it without 1 beautifull Linq Query but with 2 and some yield return:</p>
  
  <pre><code>public class LinqTestDemo
  {
      Random rand = new Random();
      List&lt;TempTable&gt; list = new List&lt;TempTable&gt;();
  
      public List&lt;TempTable&gt; GetFlatData()
      {
          list = GetTestData();
  
          var rootElement = (from x in list
                              where x.ParentID == null
                              orderby x.SortOrder
                              select x).ToList();
  
          var flatList = OrderChilds(rootElement).ToList();
  
          foreach (var tempTable in flatList)
          {
              Console.WriteLine(string.Format("ID = {0} - ParentID = {1} - Name = {2} - SortOrder = {3}", tempTable.ID, tempTable.ParentID, tempTable.Name, tempTable.SortOrder));
          }
  
          return flatList;
      }
  
      private IEnumerable&lt;TempTable&gt; OrderChilds(List&lt;TempTable&gt; enumerable)
      {
          foreach (var tempTable in enumerable)
          {
              yield return tempTable;
  
              TempTable table = tempTable;
              var childs = OrderChilds((from x in list
                                          where x.ParentID == table.ID
                                          orderby x.SortOrder
                                          select x).ToList());
  
              foreach (var child in childs)
              {
                  yield return child;
              }
          }
      }
  
      public List&lt;TempTable&gt; GetTestData()
      {
          var returnValue = new List&lt;TempTable&gt;();
          for (int i = 0; i &lt; 50; i++)
          {
              var tempTable = new TempTable();
              tempTable.ID = i;
              if (i == 0)
                  tempTable.ParentID = null;
              else
                  tempTable.ParentID = rand.Next(0, i);
  
              var maxSortOrder = (from x in returnValue
                                  where x.ParentID == tempTable.ParentID
                                  select (int?)x.SortOrder).Max();
  
              if (maxSortOrder.HasValue)
                  tempTable.SortOrder = maxSortOrder.Value + 1;
              else
                  tempTable.SortOrder = 1;
  
              tempTable.Name = string.Format("Test {0:00}", i);
              returnValue.Add(tempTable);
          }
  
          return returnValue;
      }
  
      public class TempTable
      {
          public int ID { get; set; }
          public int? ParentID { get; set; }
          public string Name { get; set; }
          public int SortOrder { get; set; }
      }
  }
  </code></pre>
  
  <p>@ Breadth-First vs Depth-First Traversal:
  After some reading I would say my desired result would be Depth-First Traversal, where the elements at the same level depth should be ordered by the property SortOrder.</p>