#using <System.dll>
#include <cmath>

using namespace System;
using namespace System::Collections::Generic;
using namespace System::Diagnostics;
using namespace System::IO;

int HeapSorts = 0;
int IntroSorts = 0;
int InsertionSorts = 0;

/*
 * -------------------------------------------------------------------
 * LoadFile
 * Purpose:
 *   Read non-blank integer records from the named input file into the program collection or shared array.
 * Parameters:
 *   fileSpec - input or output file path.
 * Returns:
 *   The loaded integer sequence or the count/status provided by this implementation.
 * Side effects:
 *   Opens and closes the input file, populates the collection or shared array, and may update its element count.
 * -------------------------------------------------------------------
 */
List<int>^ LoadFile(String^ fileSpec)
{
    Console::Write("READING INPUT FILE...");
    List<int>^ values = gcnew List<int>();
    for each (String ^ line in File::ReadLines(fileSpec))
        if (!String::IsNullOrWhiteSpace(line))values->Add(Int32::Parse(line));
    Console::WriteLine("DONE.");
    return values;
}
/*
 * -------------------------------------------------------------------
 * SaveFile
 * Purpose:
 *   Write the sorted integer collection or shared array to the named output file, one value per line.
 * Parameters:
 *   values - integer sequence to read, sort, or write; range operations modify it in place.
 *   fileSpec - input or output file path.
 * Returns:
 *   No value; writes the output file.
 * Side effects:
 *   Creates or replaces the output file and reports file progress.
 * -------------------------------------------------------------------
 */
void SaveFile(List<int>^ values, String^ fileSpec)
{
    Console::Write("SAVING OUTPUT FILE...");
    StreamWriter^ outputFile = gcnew StreamWriter(fileSpec);
    for each (int value in values)outputFile->WriteLine(value);
    outputFile->Close();
    Console::WriteLine("DONE.");
}
/*
 * -------------------------------------------------------------------
 * SiftDown
 * Purpose:
 *   Restore max-heap order below the specified root within the active heap range.
 * Parameters:
 *   values - integer sequence to read, sort, or write; range operations modify it in place.
 *   root - current heap root index.
 *   start - inclusive first index of the active range.
 *   end - exclusive end index of the active range.
 * Returns:
 *   No value; rearranges the range in place.
 * Side effects:
 *   Mutates the sequence and may stop once the heap property is restored.
 * -------------------------------------------------------------------
 */
void SiftDown(List<int>^ values, int root, int start, int end)
{
    while (start + 2 * (root - start) + 1 < end)
    {
        int child = start + 2 * (root - start) + 1;
        if (child + 1 < end && values[child] < values[child + 1]) child++;
        if (values[root] >= values[child])return;
        int temp = values[root];
        values[root] = values[child];
        values[child] = temp;
        root = child;
    }
}
/*
 * -------------------------------------------------------------------
 * Heapsort
 * Purpose:
 *   Sort the selected range in place with heapsort, the worst-case introsort fallback.
 * Parameters:
 *   values - integer sequence to read, sort, or write; range operations modify it in place.
 *   start - inclusive first index of the active range.
 *   end - exclusive end index of the active range.
 * Returns:
 *   No value; sorts the selected range in place.
 * Side effects:
 *   Mutates the range and increments the heapsort counter where present.
 * -------------------------------------------------------------------
 */
void Heapsort(List<int>^ values, int start, int end)
{
    HeapSorts++;
    for (int root = start + (end - start) / 2 - 1; root >= start; root--)SiftDown(values, root, start, end);
    for (int last = end - 1; last > start; last--)
    {
        int temp = values[start];
        values[start] = values[last];
        values[last] = temp;
        SiftDown(values, start, start, last);
    }
}
/*
 * -------------------------------------------------------------------
 * Insertionsort
 * Purpose:
 *   Sort the selected range in place with insertion sort, which is efficient for short ranges.
 * Parameters:
 *   values - integer sequence to read, sort, or write; range operations modify it in place.
 *   start - inclusive first index of the active range.
 *   end - exclusive end index of the active range.
 * Returns:
 *   No value; sorts the selected range in place.
 * Side effects:
 *   Mutates the range and increments the insertion-sort counter where present.
 * -------------------------------------------------------------------
 */
void Insertionsort(List<int>^ values, int start, int end)
{
    InsertionSorts++;
    int value, pos;
    for (int 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;
    }
}
/*
 * -------------------------------------------------------------------
 * Partition
 * Purpose:
 *   Partition the selected range around its middle-element pivot and return the first index of the right-hand range.
 * Parameters:
 *   values - integer sequence to read, sort, or write; range operations modify it in place.
 *   start - inclusive first index of the active range.
 *   end - exclusive end index of the active range.
 * Returns:
 *   The first index of the right partition, which is also the left boundary of the recursive ranges.
 * Side effects:
 *   Reorders the range in place while inward scans keep each access inside the active bounds.
 * -------------------------------------------------------------------
 */
int Partition(List<int>^ values, int start, int end)
{
    int left = start;
    int right = end - 1;
    int pivot = values[start + (end - start) / 2];
    while (left <= right)
    {
        while (values[left] < pivot)left++;
        while (values[right] > pivot)right--;
        if (left <= right)
        {
            int temp = values[left];
            values[left] = values[right];
            values[right] = temp;
            left++;
            right--;
        }
    }
    return left;
}
/*
 * -------------------------------------------------------------------
 * Introsort
 * Purpose:
 *   Sort the selected range in place: insertion sort for short ranges, heapsort when the depth budget expires, otherwise partition and recurse.
 * Parameters:
 *   values - integer sequence to read, sort, or write; range operations modify it in place.
 *   start - inclusive first index of the active range.
 *   end - exclusive end index of the active range.
 *   maxDepth - remaining partition-depth budget before heapsort fallback.
 * Returns:
 *   No value; sorts the selected range in place.
 * Side effects:
 *   Mutates the range and updates the introsort counter; recursive calls reduce the depth budget.
 * -------------------------------------------------------------------
 */
void Introsort(List<int>^ values, int start, int end, int maxDepth)
{
    IntroSorts++;
    int length = end - start;
    if (length <= 1) return;
    if (length < 16)Insertionsort(values, start, end);
    else if (maxDepth <= 0)Heapsort(values, start, end);
    else
    {
        int partition = Partition(values, start, end);
        Introsort(values, start, partition, maxDepth - 1);
        Introsort(values, partition, end, maxDepth - 1);
    }
}
/*
 * -------------------------------------------------------------------
 * PerformSort
 * Purpose:
 *   Choose the initial depth budget, time the top-level introsort, and report completion.
 * Parameters:
 *   values - integer sequence to read, sort, or write; range operations modify it in place.
 * Returns:
 *   Elapsed time measured by this implementation.
 * Side effects:
 *   Starts and stops a timer, prints progress, and invokes introsort on the full sequence.
 * -------------------------------------------------------------------
 */
double PerformSort(List<int>^ values)
{
    Console::Write("SORTING ELEMENTS...");
    Stopwatch^ timer = Stopwatch::StartNew();
    int maxDepth = values->Count > 1 ? (int)std::log2(values->Count) * 2 : 0;
    Introsort(values, 0, values->Count, maxDepth);
    timer->Stop();
    Console::WriteLine("DONE.");
    return timer->Elapsed.TotalMilliseconds;
}
/*
 * -------------------------------------------------------------------
 * main
 * Purpose:
 *   Program entry point: read the data, sort it, write the result, and report elapsed time and algorithm counts.
 * Parameters:
 *   None; this routine uses shared state or its enclosing context.
 * Returns:
 *   The runtime-specific exit status, or no value for a void entry point.
 * Side effects:
 *   Performs file I/O, invokes sorting, and prints timing and counters.
 * -------------------------------------------------------------------
 */
int main()
{
    Console::WriteLine("=======INTROSORT C++ .Net=======");
    List<int>^ values = LoadFile("D:/Sorting/Sorting_Input.txt");
    double elapsed = PerformSort(values);
    SaveFile(values, "D:/Sorting/Output_CPP_Net.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("================================");
}