Ocaml efficient quicksort

Question

I'd like to know how can write an efficient version of quicksort where list is partitioned in one pass.

I've this fragment of code,

    let rec quicksort' = function
[] -> []
| x::xs -> let small = List.filter (fun y -> y < x ) xs
           and large = List.filter (fun y -> y > x ) xs

in quicksort' small @ (x :: quicksort' large);;

but here I'm going through the list more than 1 time (calling 2 times quicksort for small and large) .

The idea is to do it in just one step without going to the list more than 1 time.

Answer 1

List.partition is the way to go:

let rec quicksort = function
    | [] -> []
    | x::xs -> let smaller, larger = List.partition (fun y -> y < x) xs
               in quicksort smaller @ (x::quicksort larger)

Notice that List.partition helps avoid one redundant traversal through xs. You still have to sort the smaller part and the larger part recursively since it's the way Quicksort works.

I have to say that this version of quicksort is far from efficient. Quicksort algorithm is an inherent in-place algorithm which mutates an input array recursively. Another factor is pivot selection; choosing the first element as the pivot is not always a good idea.

These factors lead to an extremely different implementation for efficiency (probably using Array and mutation). Quicksort on List should be used for demonstrating the idea of the algorithm and the beauty of its recursion.

Answer 2

If you need to write an efficient sort function, you may want to read this insightful paper: Engineering a sort function. Otherwise, I'm pretty sure List.sort is pretty well-written too.