i set out to compare the relative speeds of some slightly different versions of quicksort for lists.
i think the results are worth noting.


let rec qsort_else f lst =
   if lst = [] then [] else
      let pivot = List.hd lst
      let left = List.tl lst |> List.filter (f pivot) |> qsort_else f
      let right = List.tl lst |> List.filter (f pivot >> not) |> qsort_else f
      left @ [pivot] @ right

let rec qsort_append f = function
   | [] -> []
   | head :: tail ->
       (tail |> List.filter (f head) |> qsort_append f)
       @ [head] @
       (tail |> List.filter (f head >> not) |> qsort_append f)

let rec qsort_pipe f = function
   | [] -> []
   | head :: tail ->
      tail |> List.partition (f head)
      |> (fun (x, y) -> qsort_pipe f x, qsort_pipe f y)
      |> (fun (left, right) -> left @ [head] @ right)

let qsort_CPS f lst  =
   let rec sort l clst r c =
      match clst with
      | [] -> c (l @ [] @ r)
      | a :: [] -> c (l @ [a] @ r)
      | _ ->
         let pivot = List.hd clst
         let left = List.tl clst |> List.filter (f pivot)
         let right = List.tl clst |> List.filter (f pivot >> not)
         sort l left [pivot] (fun x -> sort x right r c)
   sort [] lst [] (fun x -> x)
 

i also compared these four versions with the default List.sort and the mergesort which i copied out of local.fs from the f# source (search for stable_sort).

i only tested one kind of input data: a large, unsorted list comprised of random integer data in the same range as the length of the list. specifically generated this way:

let _random = System.Random()
let rand() = _random.Next()
let num = 200000
let unsorted = [1..num] |> List.map (fun _ -> rand() % num)

i ran each sorting method on the same unsorted list five times and averaged the result in milliseconds.

these are the results using version 1.9.6.2 of the f# compiler:
List.sort: 500, 457, 525, 468, 468, --> average: 483.600000
merge sort: 510, 482, 463, 542, 467, --> average: 492.800000
qsort_else: 942, 917, 944, 968, 953, --> average: 944.800000
qsort_append: 888, 836, 854, 890, 807, --> average: 855.000000
qsort_pipe: 672, 727, 751, 788, 669, --> average: 721.400000
qsort_CPS:


conclusions:


+the continuation passing style version of quicksort overflows the stack before it returns any meaningful data. if given a much smaller dataset it is still at least 100 times slower than the other sorting methods.

+pattern matching on a list appears to be slightly faster than an if/then/else case that does the same thing.

+the fastest quicksort method pipes the list through List.partition instead of filtering twice.

+an optimized mergesort is faster than any of my quicksort implementations and this is the method that List.sort uses internally i believe.


the most interesting information though, came when i ran the same tests on the most recently released version of f#

these are the results compiled using f# 1.9.6.16:
List.sort: 1507, 1405, 1408, 1450, 1339, --> average: 1421.800000
merge sort: 834, 768, 741, 723, 706, --> average: 754.400000
qsort_else: 1125, 1104, 1051, 1099, 1013, --> average: 1078.400000
qsort_append: 1033, 946, 1000, 1073, 978, --> average: 1006.000000
qsort_pipe: 836, 860, 833, 748, 795, --> average: 814.400000
qsort_CPS:

+it is worth noting that ALL times are slightly slower but what is quite striking is:

+the native List.sort method is now almost twice as slow as my fastest quicksort method and three times slower than in the previous version of the compiler.

+since mergesort is still the fastest method (although about 60% slower than the 1.9.6.2 compiled version) and List.sort is operating so sluggishly it would lead me to believe that List.sort in the newest f# compiler no longer uses the mergesort method in local.fs.

what method does it use?