Recursive bubble sort in OCaml
Your code is easy to understand, so I can only suggest minor changes. The first thing is just a preference of mine: if a function body is nothing but a match ... with expression, I use the function keyword, instead. The second, more important recommendation is to use three clauses in the match body so you don't build a new, temporary list (hd2 :: tl) as you recurse. With both of these minor changes, sort looks like this:

let rec sort lst =
  let sorted = function
  | hd1 :: hd2 :: tl when hd1 &gt; hd2 -&gt;
        hd2 :: sort (hd1 :: tl)
  | hd1 :: tl -&gt;
        hd1 :: sort tl
  | tl -&gt; tl
in
if lst = sorted then
    lst
else
    sort sorted


As the list gets more and more sorted, the second pattern gets matched more often and simply travels down the list. Your version continues to build a new list -- even when the list is sorted.

One other thing: OCaml has an equality operator that tests for physical equality (in addition to structural equality.) So we can avoid building a new list in the second case, if it's not necessary:

| (hd1 :: tl) as lst -&gt;
    let tl' = sort tl in
    if tl' == tl then
        lst
    else
        hd1 :: tl'


Both these changes will prevent a lot of temporary objects from being created. Unfortunately, it's still a bubble sort, so it's never going to be a speed-demon. :D