module type INPUT = 
  sig
    type k
    type s
    val eq : k -> k -> bool
    val get_key : s -> k
    val is_first : s -> bool
    val is_last : s -> bool
    val printKey : k -> unit
    val lt : s -> s -> bool
  end;;

module StreamSort : 
  functor (I : INPUT) ->
    sig
      val sort : I.s Stream.t -> (I.k * I.s Stream.t) list
      val merge : (I.k * I.s Stream.t) list -> I.s Stream.t
    end;;