open Okasaki
open OrderedSig
open SortableSig

module BottomUpMergeSort (Element : Ordered) : Sortable =
struct

   module Element = Element

   type sortable = int * Element.t list list Lazy.t

   let rec mrg xs ys = 
      match xs, ys with
      | [], _ -> ys
      | _, [] -> xs
      | x::xs', y::ys' ->
         if Element.leq x y 
            then x :: mrg xs' ys
            else y :: mrg xs ys'

   let empty : sortable = (0, lazy [])

   let add x (size, segs) =
      let rec add_seg seg segs size =
         if size mod 2 = 0 
            then seg::segs
            else add_seg (mrg seg (List.hd segs)) (List.tl segs) (size / 2) in
      (size+1, lazy (add_seg [x] (!$segs) size))

   let sort (size, segs) =
      let rec mrg_all xs = function
         | [] -> xs
         | seg::segs -> mrg_all (mrg xs seg) segs 
         in
      mrg_all [] !$segs

end