This is just the F# version of the Java implementation of the dual quicksort algorithm as published on http://gdtoolbox.com/DualPivotQuicksort.pdf which is claimed to be 20% faster than normal quicksort.

(*
 * Dual-Pivot Quicksort algorithm
 * Vladimir Yaroslavskiy
 * First revision: February 16, 2009
 * Last updated: September 11, 2009
 *)

let swap (data:'a[]) i j =
  let tmp = data.[ i ]
  data.[ i ] <- data.[j]
  data.[j] <- tmp

let rec insertSortExtendedAux (data:'a[]) left right i j =
  if i <= right then
    if j > left && data.[j] < data.[j - 1] then
      swap data j (j - 1)
      insertSortExtendedAux data left right i (j - 1)
    else
      insertSortExtendedAux data left right (i+1) (i+1)
let insertSortExtended data left right =
  insertSortExtendedAux data left right (left+1) (left+1)

let ArrayDivisor = 3

let rec dualQuickSortExtended data left right =
  let len = right - left
  if len < 27 then
    insertSortExtended data left right
  else
    let third = len /  ArrayDivisor

    //medians
    let mutable m1 = left + third
    let mutable m2 = right - third

    if m1 <= left then m1 <- left + 1
    if m2 >= right then m2 <- right - 1

    if data.[m1] < data.[m2] then
      swap data m1 left
      swap data m2 right
    else
      swap data m1 right
      swap data m2 left

    //pivots
    let pivot1 = data.[left]
    let pivot2 = data.[right]

    //pointers
    let less = ref <| left + 1
    let great = ref <| right - 1

    let inline pivotAroundLess k =
      swap data k !less
      incr less

    let inline pivotAroundGreat k =
      swap data k !great
      decr great

    //sorting
    for k in !less .. !great do
      if data.[k] < pivot1 then
        pivotAroundLess k
      elif data.[k] > pivot2 then
        while k < !great && data.[!great] > pivot2 do decr great
        pivotAroundGreat k
        if data.[k] < pivot1 then
          pivotAroundLess k

    //swaps
    let dist =
      let delta = !great - !less
      if delta < 13 then delta + 1 else delta

    swap data (!less - 1) left
    swap data (!great + 1) right

    //subarrays
    dualQuickSortExtended data left (!less - 2)
    dualQuickSortExtended data (!great + 2) right

    if dist > len - 13 && pivot1 <> pivot2 then
      for k in !less .. !great do
      if data.[k] = pivot1 then
        pivotAroundLess k
      elif data.[k] = pivot2 then
        pivotAroundGreat k
        if data.[k] = pivot1 then
          pivotAroundLess k

    //subarray
    if pivot1 < pivot2 then
      dualQuickSortExtended data !less !great

let checkRange data i j s =
  if i < 0 then invalidArg "i" (sprintf "%s : lower index was out of bounds" s)
  if j >= Array.length data then invalidArg "j" (sprintf "%s : upper index was out of bounds" s)

let sort data fromPos toPos =
  checkRange data fromPos toPos "sort data fromPos toPos"
  dualQuickSortExtended data fromPos toPos

let runExample ()=
  let data = Array.init 50 (fun i -> i % 10)
  printf "before : %A" data
  sort data 0 (data.Length - 1)
  printf "after : %A" data