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
    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
    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
    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
    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
    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
    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
    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
    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
    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