Imports System.Threading
Imports System.Threading.Tasks

Module Module1

    Sub Main()
        coreCount = Environment.GetEnvironmentVariable("NUMBER_OF_PROCESSORS")
        Console.WriteLine("Number Of Cores: {0}", coreCount)
        InitializeArray()
        CheckSorting()
        Dim StartTimer As New Stopwatch
        StartTimer.Start()
        MergeSortSequential(0, Length)
        StartTimer.Stop()
        Console.WriteLine("Algorithm is done for {0} ms", StartTimer.ElapsedMilliseconds)
        StartTimer.Reset()
        CheckSorting()
        Array = New List(Of Integer)
        InitializeArray()
        CheckSorting()
        StartTimer.Start()
        MergeSortConcurrent(0, Length)
        StartTimer.Stop()
        Console.WriteLine("Algorithm is done for {0} ms", StartTimer.ElapsedMilliseconds)
        CheckSorting()
        Console.ReadLine()
    End Sub

    Dim Length As Integer = 1000000
    Dim Array As List(Of Integer) = New List(Of Integer)
    Dim Temp As List(Of Integer) = New List(Of Integer)
    Dim coreCount As Integer

    Public Sub InitializeArray()
        Randomize()
        For i = 0 To Length - 1
            Array.Add(CInt(Int((1000000 * Rnd()) + 1)))
            Temp.Add(0)
        Next
    End Sub

    Public Sub PrintArray()
        Console.Write("Array: ")
        For i = 0 To Array.Count - 1
            Console.Write($"{Array(i)} ")
        Next
        Console.WriteLine()
    End Sub

    Public Sub CheckSorting()
        For i = 0 To Array.Count - 2
            If Array(i) > Array(i + 1) Then
                Console.WriteLine("Array is not sorted")
                Return
            End If
        Next
        Console.WriteLine("Array is sorted")
    End Sub

    Public Sub MergeSortConcurrent(ByVal Start As Integer, ByVal Length As Integer)
        If Length <= Module1.Length / coreCount Then
            MergeSortSequential(Start, Length)
            Return
        End If
        Dim Limit As Integer = If(Length Mod 2 = 1, Math.Floor(Length / 2) + 1, Math.Floor(Length / 2))
        Dim Branches As New List(Of Task)
        Branches.Add(Task.Run(Sub() MergeSortConcurrent(Start, Limit)))
        Branches.Add(Task.Run(Sub() MergeSortConcurrent(Start + Limit, Math.Floor(Length / 2))))
        Dim t As Task = Task.WhenAll(Branches)
        t.Wait()
        Merge(Start, Length)
        Return
    End Sub

    Public Sub MergeSortSequential(ByVal Start As Integer, ByVal Length As Integer)
        If Length < 2 Then
            Return
        End If
        If Length = 2 Then
            If Array(Start) > Array(Start + 1) Then
                Dim Temp = Array(Start)
                Array(Start) = Array(Start + 1)
                Array(Start + 1) = Temp
            End If
            Return
        End If
        Dim Limit As Integer = If(Length Mod 2 = 1, Math.Floor(Length / 2) + 1, Math.Floor(Length / 2))
        MergeSortSequential(Start, Limit)
        MergeSortSequential(Start + Limit, Math.Floor(Length / 2))
        Merge(Start, Length)
    End Sub

    Public Sub Merge(ByVal Start As Integer, ByVal Length As Integer)
        Dim i As Integer = Start
        Dim Limit As Integer = If(Length Mod 2 = 1, Math.Floor(Length / 2) + 1, Math.Floor(Length / 2))
        Dim j As Integer = Start + Limit
        Dim TmpList As New List(Of Integer)
        While i < Start + Limit And j < Start + Length
            If Array(i) < Array(j) Then
                TmpList.Add(Array(i))
                i += 1
            Else
                TmpList.Add(Array(j))
                j += 1
            End If
        End While
        While i < Start + Limit
            TmpList.Add(Array(i))
            i += 1
        End While
        While j < Start + Length
            TmpList.Add(Array(j))
            j += 1
        End While
        For k = Start To Start + Length - 1
            Array(k) = TmpList(k - Start)
        Next
    End Sub

End Module