using System.Diagnostics;

namespace Introsort
{
    internal class Program
    {
        private static int HeapSorts = 0;
        private static int InsertionSorts = 0;
        private static int IntroSorts = 0;
        private static List<int> LoadFile(string fileSpec)
        {
            Console.Write("READING INPUT FILE...");
            var values = new List<int>();
            foreach(var line in File.ReadLines(fileSpec))
            {
                if(!string.IsNullOrWhiteSpace(line))values.Add(int.Parse(line));
            }
            Console.WriteLine("DONE.");
            return values;
        }
        private static void SaveFile(List<int> values, string fileSpec)
        {
            Console.Write("SAVING OUTPUT FILE...");
            File.WriteAllLines(fileSpec, values.ConvertAll(v=>v.ToString()));
            Console.WriteLine("DONE.");
        }
        private static void SiftDown(List<int> values,int root, int start, int end)
        {
            while (start + 2 * (root - start) + 1 < end)
            {
                var child = start + 2 * (root - start) + 1;
                if (child + 1 < end && values[child] < values[child + 1]) child++;
                if (values[root] >= values[child]) return;
                (values[root], values[child]) = (values[child], values[root]);
                root = child;
            }
        }
        private static void Heapsort(List<int> values, int start, int end)
        {
            HeapSorts++;
            for (var root = start + (end - start) / 2 - 1; root >= start; root--) SiftDown(values, root, start, end);
            for(var last = end - 1; last > start; last--)
            {
                (values[start], values[last]) = (values[last], values[start]);
                SiftDown(values, start, start, last);
            }
        }
        private static void Insertionsort(List<int> values, int start, int end)
        {
            InsertionSorts++;
            int value, pos;
            for (var index = start; index < end; index++)
            {
                value = values[index];
                pos = index - 1;
                while (pos >= start && values[pos] > value)
                {
                    values[pos + 1] = values[pos];
                    pos--;
                }
                values[pos + 1] = value;
            }
        }
        private static int Partition(List<int> values, int start, int end)
        {
            var left = start;
            var right = end - 1;
            var pivot = values[start + (end - start) / 2];
            while (left <= right)
            {
                while (values[left] < pivot) left++;
                while (values[right] > pivot) right--;
                if (left <= right)
                {
                    (values[left], values[right]) = (values[right], values[left]);
                    left++;
                    right--;
                }
            }
            return left;
        }

        private static void Introsort(List<int> values, int start, int end, int maxDepth)
        {
            IntroSorts++;
            var length = end - start;
            if (length <= 1) return;
            if (length < 16) Insertionsort(values, start, end);
            else if (maxDepth <= 0) Heapsort(values, start, end);
            else
            {
                var partition = Partition(values, start, end);
                Introsort(values, start, partition, maxDepth - 1);
                Introsort(values, partition, end, maxDepth - 1);
            }
        }

        private static double PerformSort(List<int> values)
        {
            Console.Write("SORTING ELEMENTS...");
            var timer = Stopwatch.StartNew();
            var maxDepth = values.Count > 1 ? (int)Math.Log2(values.Count) * 2 : 0;
            Introsort(values, 0, values.Count, maxDepth);
            timer.Stop();
            Console.WriteLine("DONE.");
            return timer.Elapsed.TotalSeconds;
        }
        static void Main(string[] args)
        {
            Console.WriteLine("==========INTROSORT C#==========");
            List<int> values = LoadFile("D:/Sorting/Sorting_Input.txt");
            double elapsed = PerformSort(values);
            SaveFile(values, "D:/Sorting/Output_CSharp.txt");
            Console.WriteLine("==========RUN COMPLETE==========");
            Console.WriteLine("INTROSORT TOOK {0:F6} SECONDS.", elapsed);
            Console.WriteLine("================================");
            Console.WriteLine("SORT CALLED | TIMES");
            Console.WriteLine("------------+-------------------");
            Console.WriteLine("Intro       | {0}", IntroSorts);
            Console.WriteLine("Insertion   | {0}", InsertionSorts);
            Console.WriteLine("Heap        | {0}", HeapSorts);
            Console.WriteLine("================================");

        }
    }
}
ok,