(******************************************************************
* INSERTION SORT
******************************************************************)
(* [insert x lst] is a list containing all the elements of [lst] as
* well as [x], sorted according to the built-in operator [>=].
* requires: [lst] is already sorted according to [<=] *)
let rec insert x = function
| [] -> [x]
| h::t ->
if h >= x
then x::h::t
else h::(insert x t)
(* [ins_sort lst] is [lst] sorted according to the built-in operator [<=].
* performance: O(n^2) time, where n is the number of elements in [lst].
* Not tail recursive. *)
let rec ins_sort = function
| [] -> []
| h::t -> insert h (ins_sort t)
(******************************************************************
* MERGE SORT
******************************************************************)
(* [take k lst] is the first [k] elements of [lst], or just [lst]
* if it has fewer than [k] elements.
* requires: [k>=0] *)
let rec take k = function
| [] -> []
| h::t ->
if k=0
then []
else h::(take (k-1) t)
(* [drop k lst] is all but the first [k] elements of [lst], or just []
* if it has fewer than [k] elements.
* requires: [k>=0] *)
let rec drop k = function
| [] -> []
| _::t as lst ->
if k=0
then lst
else drop (k-1) t
(* [merge xs ys] is a list containing all the elements of [xs] as well as [ys],
* in sorted order according to [<=].
* requires: [xs] and [ys] are both already sorted according to [<=]. *)
let rec merge xs ys =
match xs, ys with
| [], _ -> ys
| _, [] -> xs
| x::xs', y::ys' ->
if x <= y
then x::(merge xs' ys)
else y::(merge xs ys')
(* [merge_sort lst] is [lst] sorted according to the built-in operator [<=].
* performance: O(n log n) time, where n is the number of elements in [lst].
* Not tail recursive. *)
let rec merge_sort = function
| [] -> []
| [x] -> [x]
| xs ->
let k = (List.length xs) / 2 in
merge
(merge_sort (take k xs))
(merge_sort (drop k xs))