Imports System
Imports System.Diagnostics
Imports System.Collections.Generic
Imports System.IO

Module Program
    Dim HeapSorts As Integer = 0
    Dim InsertionSorts As Integer = 0
    Dim IntroSorts As Integer = 0
    ' -------------------------------------------------------------------
    ' LoadFile
    ' Purpose:
    '   Read non-blank integer records from the named input file into the program collection or shared array.
    ' Parameters:
    '   fileSpec - input path whose non-blank lines are parsed as integers.
    ' 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.
    ' -------------------------------------------------------------------
    Function LoadFile(fileSpec As String) As List(Of Integer)
        Console.Write("READING INPUT FILE...")
        Dim values As New List(Of Integer)()
        For Each line In File.ReadLines(fileSpec)
            If Not String.IsNullOrWhiteSpace(line) Then
                values.Add(Integer.Parse(line))
            End If
        Next
        Console.WriteLine("DONE.")
        Return values
    End Function
    ' -------------------------------------------------------------------
    ' SaveFile
    ' Purpose:
    '   Write the sorted integer collection or shared array to the named output file, one value per line.
    ' Parameters:
    '   values - integer list to write, in its current order.
    '   fileSpec - output path to create or replace.
    ' Returns:
    '   No value; writes the output file.
    ' Side effects:
    '   Creates or replaces the output file and reports file progress.
    ' -------------------------------------------------------------------
    Sub SaveFile(values As List(Of Integer), fileSpec As String)
        Console.Write("SAVING OUTPUT FILE...")
        File.WriteAllLines(fileSpec, values.ConvertAll(Function(value) value.ToString()))
        Console.WriteLine("DONE.")
    End Sub
    ' -------------------------------------------------------------------
    ' SiftDown
    ' Purpose:
    '   Restore max-heap order below the specified root within the active heap range.
    ' Parameters:
    '   values - integer list whose heap range is modified.
    '   root - current root index to sift down.
    '   start - inclusive first index of this heap range.
    '   finish - exclusive end index of this heap range.
    ' Returns:
    '   No value; rearranges the range in place.
    ' Side effects:
    '   Mutates the sequence and may stop once the heap property is restored.
    ' -------------------------------------------------------------------
    Sub SiftDown(values As List(Of Integer), root As Integer, start As Integer, finish As Integer)
        While start + 2 * (root - start) + 1 < finish
            Dim child = start + 2 * (root - start) + 1
            If child + 1 < finish AndAlso values(child) < values(child + 1) Then child = child + 1
            If values(root) >= values(child) Then Exit Sub
            Dim temp As Integer = values(root)
            values(root) = values(child)
            values(child) = values(root)
            root = child
        End While
    End Sub
    ' -------------------------------------------------------------------
    ' Heapsort
    ' Purpose:
    '   Sort the selected range in place with heapsort, the worst-case introsort fallback.
    ' Parameters:
    '   values - integer list whose range is sorted in place.
    '   start - inclusive first index of the range.
    '   finish - exclusive end index of the range.
    ' Returns:
    '   No value; sorts the selected range in place.
    ' Side effects:
    '   Mutates the range and increments the heapsort counter where present.
    ' -------------------------------------------------------------------
    Sub Heapsort(values As List(Of Integer), start As Integer, finish As Integer)
        HeapSorts = HeapSorts + 1
        For root = start + (finish - start) / 2 - 1 To start Step -1
            SiftDown(values, root, start, finish)
        Next
        For last = finish - 1 To start + 1 Step -1
            Dim temp = values(start)
            values(start) = values(last)
            values(last) = temp
            SiftDown(values, start, start, last)
        Next
    End Sub
    ' -------------------------------------------------------------------
    ' InsertionSort
    ' Purpose:
    '   Sort the selected range in place with insertion sort, which is efficient for short ranges.
    ' Parameters:
    '   values - integer list whose range is sorted in place.
    '   start - inclusive first index of the range.
    '   finish - exclusive end index of the range.
    ' Returns:
    '   No value; sorts the selected range in place.
    ' Side effects:
    '   Mutates the range and increments the insertion-sort counter where present.
    ' -------------------------------------------------------------------
    Sub InsertionSort(values As List(Of Integer), start As Integer, finish As Integer)
        InsertionSorts = InsertionSorts + 1
        Dim value As Integer
        Dim pos As Integer
        For index = start To finish - 1
            value = values(index)
            pos = index - 1
            While pos >= start AndAlso values(pos) > value
                values(pos + 1) = values(pos)
                pos = pos - 1
            End While
            values(pos + 1) = value
        Next
    End Sub
    ' -------------------------------------------------------------------
    ' Partition
    ' Purpose:
    '   Partition the selected range around its middle-element pivot and return the first index of the right-hand range.
    ' Parameters:
    '   values - integer list whose range is rearranged in place.
    '   start - inclusive first index of the range.
    '   finish - exclusive end index of the 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.
    ' -------------------------------------------------------------------
    Function Partition(values As List(Of Integer), start As Integer, finish As Integer) As Integer
        Dim left As Integer = start
        Dim right As Integer = finish - 1
        Dim pivot As Integer = values(start + (finish - start) / 2)
        While left <= right
            While values(left) < pivot
                left = left + 1
            End While
            While values(right) > pivot
                right = right - 1
            End While
            If left <= right Then
                Dim temp = values(left)
                values(left) = values(right)
                values(right) = temp
                left = left + 1
                right = right - 1
            End If
        End While
        Return left
    End Function
    ' -------------------------------------------------------------------
    ' 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 list whose range is sorted in place.
    '   start - inclusive first index of the range.
    '   finish - exclusive end index of the range.
    '   maxDepth - remaining partition 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.
    ' -------------------------------------------------------------------
    Sub Introsort(values As List(Of Integer), start As Integer, finish As Integer, maxDepth As Integer)
        IntroSorts = IntroSorts + 1
        Dim length As Integer = finish - start
        If length <= 1 Then Exit Sub
        If length < 16 Then
            InsertionSort(values, start, finish)
        ElseIf maxDepth <= 0 Then
            Heapsort(values, start, finish)
        Else
            Dim part As Integer = Partition(values, start, finish)
            Introsort(values, start, part, maxDepth - 1)
            Introsort(values, part, finish, maxDepth - 1)
        End If
    End Sub
    ' -------------------------------------------------------------------
    ' PerformSort
    ' Purpose:
    '   Choose the initial depth budget, time the top-level introsort, and report completion.
    ' Parameters:
    '   values - complete integer list to sort 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.
    ' -------------------------------------------------------------------
    Function PerformSort(values As List(Of Integer)) As Double
        Console.Write("SORTING ELEMENTS...")
        Dim timer = Stopwatch.StartNew()
        Dim maxDepth As Integer = 0
        If values.Count > 1 Then maxDepth = Math.Log2(values.Count) * 2
        Introsort(values, 0, values.Count, maxDepth)
        timer.Stop()
        Console.WriteLine("DONE.")
        Return timer.Elapsed.TotalSeconds
    End Function
    ' -------------------------------------------------------------------
    ' Main
    ' Purpose:
    '   Program entry point: read the data, sort it, write the result, and report elapsed time and algorithm counts.
    ' Parameters:
    '   args - command-line arguments supplied by the runtime (unused here).
    ' 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.
    ' -------------------------------------------------------------------
    Sub Main(args As String())
        Console.WriteLine("=======INTROSORT VB .NET========")
        Dim values As List(Of Integer) = LoadFile("D:\Sorting\Sorting_Input.txt")
        Dim elapsed As Double = PerformSort(values)
        SaveFile(values, "D:\Sorting\Output_VB_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("================================")
    End Sub
End Module