//quick sort
let quickSort (a : 'a[]) =
    let rand = new Random() //for random pivot chosing
    //swaps elements of array a with indeces i and j
    let swap (a : 'a[]) i j =
        let temp = a.[i]
        a.[i] <- a.[j]
        a.[j] <- temp

    //sorts array's a subarray [l; r) in-place
    let rec quickSortRange (a : 'a[]) l r =
        match r - l with
        | 0 | 1 -> ()
        | n ->
            //preprocess: swap pivot to 1st position
            swap a l <| rand.Next(l, r)
            let p = a.[l]
            //scan and partitioning
            let mutable i = l + 1 //left from i <=> less than pivot part
            for j in (l+1)..(r-1) do
                //preserve invariant: [p|  <p |i >p  |j  unpartitioned  ]
                if a.[j] < p then
                    swap a j i
                    i <- i + 1
            swap a (i-1) l //place pivot in appropriate pos.
            quickSortRange a l (i-1)
            quickSortRange a i r

    quickSortRange a 0 a.Length