An OCAML implementation of the Odd/Even Quick Sort Algorithm

This is a simple implementation of the Odd/Even Quick Sort Algorithm in OCAML.

This algorithm orders even numbers before the odds numbers. Eg: given the numbers 6,3,1,2,4,5 it will return 2,4,6,1,3,5

(*
Fabio Varesano - 2007/05/11
Quick sort Odd-even

final order will be:
as example: 2,4,6,1,3,7
*)


let leq a b = if ( (a mod 2==0 && b mod 2==1) || ((a mod 2==0 && b mod 2==0) && a<=b) || ((a mod 2==1 && b mod 2==1) && a<=b)) then true else false;;

let rec quicksort leq list =
  match list with
  | [] -> []
  | [x] -> [x]
  | pivot::rest ->
      let rec partition left right list =
        match list with
        | [] -> quicksort leq left @ (pivot :: quicksort leq right)
        | head::tail -> if leq head pivot then partition (head::left) right tail
                                         else partition left (head::right) tail
      in partition [] [] rest;;


quicksort leq [3;4;6;1;9;20;5;7;4;2;8];;