using System;

using System.Diagnostics;

using System.Linq;

using System.Text;

using System.Collections.Generic;

​

public class Block 

{

    public string Name { get; set;  }

    public string BlockName { get; set; }

    public string PreviousBlockName { get; set; }

    public override string ToString() {

        return $"Name:{Name} BlockName:{BlockName} PreviousBlockName:{PreviousBlockName}";

    }

}

​

public class Program

{

    public static void Main()

    {

        //IGNORE, not part of algorithm////////////////////////////////////////

        var howMuchSampleDataToGenerate = 1000;

        var unsorted = GetSampleData(howMuchSampleDataToGenerate);

        //////////////////////////////////////////////////////////////////////

​

        var sw = new Stopwatch(); 

        sw.Start();

​

        //create a HashSet with all the block names

        var blockNames = unsorted.Select(x => x.BlockName).ToHashSet();               // *COST* 200K loops

        //The first item is the one where the PreviousBlockName is not in the blockNames HashSet

        var first = unsorted.First(x => !blockNames.Contains(x.PreviousBlockName));   // *COST* MAX 200K loops, but could be less depending where the first item is at

        //Now we create a dictionary with the Key being the PreviousBlockName

        //We also make sure not to include the "first" item that we got from above

        var dictionary = unsorted                                 

            .Where(x => x.BlockName != first.BlockName)       // !IMPORTANT! Make sure the first Block is not included in said dictionary

            .ToDictionary(block => block.PreviousBlockName);  // *COST* 200K

​

​

        //we create our array with the same sise as the unsorted list

        var sorted = new Block[unsorted.Count];

        sorted[0] = first;                       //add the first item to index 0 of the array

        var current = first;                     //make our "current" variable point to the "first" item, defo needs this

​

​

        /* MAIN ALGORITHM SECTION */

        for (var i = 0; i < dictionary.Count; i++)   //*COST* 200K

        {

            //The 3 lines below is the magic! :D

            var next = dictionary[current.BlockName];

            sorted[i+1] = next;

            current = next;

        }

        sw.Stop();

        Console.WriteLine($"Total time to sort in milliseconds: {sw.ElapsedMilliseconds}");

    }

    //IGNORE THIS, it's only generating some sample data

    public static List<Block> GetSampleData(int amount) 

    {

         var unsorted = Enumerable.Range(0, amount)

                             .Select((x) =>

                             {

                                 return new Block()

                                 {

                                     Name = x.ToString(),

                                     BlockName = CreateMd5(x),

                                     PreviousBlockName = CreateMd5(x - 1)

                                 };

                             })

                             .ToList();

        unsorted.Reverse();

        return unsorted;

    }

    //TOTALLY IGNORE THIS METHOD, not part of the algorithm//

    public static string CreateMd5(int x)

    {

        var input = x.ToString();

        // Use input string to calculate MD5 hash

        using (System.Security.Cryptography.MD5 md5 = System.Security.Cryptography.MD5.Create())

        {

            byte[] inputBytes = System.Text.Encoding.ASCII.GetBytes(input);

            byte[] hashBytes = md5.ComputeHash(inputBytes);

​

            // Convert the byte array to hexadecimal string

            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < hashBytes.Length; i++)

            {

                sb.Append(hashBytes[i].ToString("X2"));

            }

            return sb.ToString();

        }

    }

}