let testDestructiveSort (sort : int [] -> unit) =
   let test input expected =
      let result = input |> List.toArray
      sort result
      let res = result |> List.ofArray
      if res = expected then
         printfn "[ OK ] sort %A -> %A" input expected
      else
         printfn "[FAIL] sort %A -> %A != %A" input res expected
   test [] []
   test [1] [1]
   test [1; 2] [1; 2]
   test [2; 1] [1; 2]
   test [1; 3; 2] [1; 2; 3]
   test [2; 1; 1] [1; 1; 2]
   test [5; 4; 3; 2; 1] [1; 2; 3; 4; 5]

let arraySortD (arr : int []) =
   let rnd = new System.Random()
   let partition lo hi =
         let p = rnd.Next(lo, hi)
         let pivot = arr.[p]
         let mutable i = lo - 1
         let mutable j = hi + 1
         while i < j do
            i <- i + 1
            while arr.[i] < pivot do
               i <- i + 1
            j <- j - 1
            while arr.[j] > pivot do
               j <- j - 1
            if i < j then
               let tmp = arr.[i]
               arr.[i] <- arr.[j]
               arr.[j] <- tmp
         j
   let rec qsort lo hi =
      if lo < hi then
         let p = partition lo hi
         qsort lo p
         qsort (p + 1) hi
   qsort 0 (arr.Length - 1)

testDestructiveSort arraySortD