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
0

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


let checkSort (arr:int[], length:int) =
   let mutable a = 1
   for x=0 to length-2 do
    if (arr.[x]>arr.[x+1]) then a<-0
   if a=1 then printfn "Sorting is correct." else printfn "Sorting is NOT correct."

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))
   Sort(4, arr, 0 , length-1)
   checkSort(arr, length)
   arr


[<EntryPoint>]
let main argv =

    0 // return an integer exit code

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