(******************************************************************
* 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))