letrec insertionSort lst = match lst with |  ->  | x :: nl -> insert x (insertionSort nl) and insert ele ls = match ls with |  ->  | x :: nl -> if ele < x then ele :: x :: nl else x :: insert ele nl ;;
2. bubble sort (like c)
1 2 3 4 5 6 7 8 9 10 11 12 13 14
let bubbleSort array = let len = Array.length arrayin for i = 0to len - 2do for j = 0to len - 2 - i do if (array.(j) > array.(j+1)) then ( let tem = array.(j) in array.(j) <- array.(j+1); array.(j+1) <- tem; ) done done ;;
letrec bubbleSortList lst = let nl = swap lst in if lst <> nl then bubbleSortList nl else lst ;;
The above implementation could be written as following:
1 2 3 4 5 6 7 8 9 10
letrec bubbleSortList list = let sorted = matchlistwith | hd1::hd2::tl when hd1 > hd2 ->hd2::soryList (hd1::tl) | hd1::tl -> hd1::bubbleSortList tl | tl -> tl in iflist = sorted thenlist else bubbleSortList sorted ;;
4. merge sort
OCaml provides the sort module , the algorithm used in sort module is merging sort. Let us implement it by ourselves. The merge sort code in C++ is presented in sort list. We write it in OCaml which has the identical idea.
The first step, we need to have a merge function merging two sorted lists. The second function is the splitting which is used to split a list into two halves. In the version of C++, the list is split at the middle position while in this version, the new two half lists select elements from the original list one by one.
partition p l returns a pair of lists (l1, l2), where l1 is the list of all the elements of l that satisfy the predicate p, and l2 is the list of all the elements of l that do not satisfy p. The order of the elements in the input list is preserved.
We can also write this function by ourselves:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
let partition p l = letrec part left right lst = match lst with |  -> ( left,right) | hd :: nl -> if p hd then part (hd::left) right nl else part left (hd::right) nl in part  l ;;
letrec quickSort lst = match lst with |  ->  | pivot :: rest -> let left, right = List.partition ((>) pivot) rest in quickSort left @ pivot :: quickSort right ;;