merge-sorted.ml

(* Merge two pre-sorted lists into another sorted list *)

let rec merge_sorted left right =              
  match left, right with
  | left_head :: left_tail, right_head :: right_tail ->
      if left_head < right_head then
        left_head :: merge_sorted left_tail right
      else
        right_head :: merge_sorted left right_tail
  | [], rest | rest, [] -> rest

let () =
  assert (merge_sorted [1; 1; 1; 2; 30; 40] [15; 30; 35; 50] = [1; 1; 1; 2; 15; 30; 30; 35; 40; 50])
  
(* Tail-recursive, returning reversed-sorted list *)

let rec merge_sorted_reverse ?(accumulator=[]) left right =              
  match left, right with
  | left_head :: left_tail, right_head :: right_tail ->
      if left_head < right_head then
        merge_sorted_reverse ~accumulator:(left_head :: accumulator) left_tail right
      else
        merge_sorted_reverse ~accumulator:(right_head :: accumulator) left right_tail
  | [], rest | rest, [] -> rest @ accumulator