module MergeSort
open System
open System.Threading
open System.Diagnostics

let Merge (arr:int[], left:int, middle:int, right:int) =
    let mutable m1 = middle - left + 2
    let mutable m2 = right - middle + 1
    let L = Array.create m1 0
    let R = Array.create m2 0
    m1<-m1-1
    m2<-m2-1
    for i = 0 to m1-1 do L.[i] <- arr.[i+left]
    for i=0 to m2-1 do R.[i] <- arr.[i+middle+1]
    L.[m1]<-System.Int32.MaxValue
    R.[m2]<-System.Int32.MaxValue
    let mutable i = 0
    let mutable j = 0

    for x=left to right do
     if (L.[i]<R.[j]) then do
      arr.[x]<-L.[i]
      i<-i+1
     else do
      arr.[x]<-R.[j]
      j<-j+1


let rec Sort (threadMaxNumber:int , arr: int[], left:int, right:int) =
    if (left < right && threadMaxNumber>1) then do
       let middle = left + (right-left)/2
       let t = new Thread(ThreadStart(fun _ -> Sort (threadMaxNumber/2, arr, left, middle)))
       t.Start()
       Sort(threadMaxNumber/2, arr, middle+1, right)
       t.Join()
       Merge(arr, left, middle, right)
        else if (left<right) then do
        let middle = left + (right-left)/2
        Sort (threadMaxNumber/2, arr, left, middle)
        Sort(threadMaxNumber/2, arr, middle+1, right)
        Merge(arr, left, middle, right)


let createArr (degree:float, threadNumber:int) =
   let length = Int32.Parse(System.Math.Pow(10.0, degree).ToString())
   let rnd = new System.Random(0)
   let arr = Array.init length (fun i -> rnd.Next(0, length))
   let timer = new System.Diagnostics.Stopwatch()
   timer.Start()
   Sort(threadNumber, arr, 0 , length-1)
   timer.Stop()
   let mutable a = 1
   for x=0 to length-2 do
    if (arr.[x]>arr.[x+1]) then a<-0
   //printfn "%s %A" "Sorting time: " timer.Elapsed.TotalSeconds
   a

[<EntryPoint>]
let main argv =

    0 // return an integer exit code


//[<TestCase (6.0,1, Result = 1)>]
//[<TestCase (7.0,4, Result = 1)>]
//let ``Test`` (d : float, t : int) =
  //createArr d t