using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    private static IList<ParentChild> parentChildList;

    public static void Main()

    {

        SetupTestData1();

        Sort(parentChildList);

        OutputList();

        SetupTestData2();

        Sort(parentChildList);

        OutputList();

    }

    public static void Sort(IList<ParentChild> pcList)

    {

        for(int i = 0; i < pcList.Count; i++)

        {

            // If item exists later in list with childid = our parentid, move past that one

            var ancestor = pcList

                .Skip(i+1)

                .LastOrDefault(x => x.ChildId == pcList[i].ParentId);

            if (ancestor != null)

            {                    

                var iAnc = pcList.IndexOf(ancestor);

                System.Console.WriteLine("Moving {0}/{1} to {2}", pcList[i].ParentId, pcList[i].ChildId, iAnc);

                pcList.Insert(iAnc+1, pcList[i]);

                pcList.RemoveAt(i);

                i--;

            }

        }

    }

    public static void SetupTestData1()

    {

        parentChildList = new List<ParentChild>();

        parentChildList.Add(new ParentChild { ParentId = 5, ChildId = 6 });

        parentChildList.Add(new ParentChild { ParentId = 1, ChildId = 5 });

        parentChildList.Add(new ParentChild { ParentId = 3, ChildId = 4 });

        parentChildList.Add(new ParentChild { ParentId = 2, ChildId = 3 });

        parentChildList.Add(new ParentChild { ParentId = 1, ChildId = 2 });

    }

    public static void SetupTestData2()

    {

        parentChildList = new List<ParentChild>();

        parentChildList.Add(new ParentChild { ParentId = 3, ChildId = 4 });

        parentChildList.Add(new ParentChild { ParentId = 2, ChildId = 3 });

        parentChildList.Add(new ParentChild { ParentId = 6, ChildId = 7 });

        parentChildList.Add(new ParentChild { ParentId = 5, ChildId = 6 });

        parentChildList.Add(new ParentChild { ParentId = 1, ChildId = 5 });

        parentChildList.Add(new ParentChild { ParentId = 1, ChildId = 2 });

    }

    public static void OutputList()

    {

        foreach(var pc in parentChildList)

        {

            System.Console.WriteLine("{0}/{1}", pc.ParentId, pc.ChildId);   

        }

    }

    public class ParentChild

    {

        public int ParentId { get; set; }

        public int ChildId { get; set; }

    }

}