(* Merge sort.
   Copyright (C) 2003 Jean Goubault-Larrecq and LSV, CNRS UMR 8643 & ENS Cachan.

   This file is part of h1.

   h1 is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   h1 is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with h1; see the file COPYING.  If not, write to
   the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
*)

fun merge less =
    let fun merge ([],l2) = l2
	  | merge (l1,[]) = l1
	  | merge (l1 as x1::l'1,l2 as x2::l'2) =
	    if less(x1,x2)
		then x1::merge(l'1,l2)
	    else x2::merge(l1,l'2)
    in
	merge
    end;

fun sort less = (* (''a * ''a -> bool) -> (''a -m> 'b) -> ''a list *)
    let val merge = merge less
	fun sort {} = []
	  | sort {x => _} = [x]
	  | sort vars =
	    let val (vars1,vars2) = split vars
	    in
		merge (sort vars1,sort vars2)
	    end
    in
	sort
    end;

fun merge_pairs less =
    let fun merge (nil, l2) = l2
	  | merge (l1, nil) = l1
	  | merge (l1 as (e1 as (x1, _))::l'1,
		   l2 as (e2 as (x2, _))::l'2) =
	    if less (x1, x2)
		then e1::merge (l'1, l2)
	    else e2::merge (l1, l'2)
    in
	merge
    end;

fun sort_pairs less =
    let val merge = merge_pairs less
	fun sort {} = nil
	  | sort {x => y} = [(x, y)]
	  | sort vars =
	    let val (vars1, vars2) = split vars
	    in
		merge (sort vars1, sort vars2)
	    end
    in
	sort
    end;

fun least less =
    let fun find {} = raise Empty
	  | find {x => _} = x
	  | find xs = let val (xs1,xs2) = split xs
			  val x1 = find xs1
			  val x2 = find xs2
		      in
			  if less (x1,x2)
			      then x1
			  else x2
		      end
    in
	find
    end
