remise au gout du jour du repertoire theories/Sorting de la V6.3

git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@2231 85f007b7-540e-0410-9357-904b9bb8a0f7

4 files changed, 149 insertions, 130 deletions

diff --git a/.depend b/.depend
index 83fcf10447..ffc16c0564 100644
--- a/.depend
+++ b/.depend
@@ -24,14 +24,15 @@ kernel/typeops.cmi: kernel/environ.cmi kernel/names.cmi kernel/sign.cmi \
     kernel/term.cmi kernel/univ.cmi 
 kernel/univ.cmi: kernel/names.cmi lib/pp.cmi 
 lib/pp.cmi: lib/pp_control.cmi 
+lib/system.cmi: lib/pp.cmi 
+lib/util.cmi: lib/pp.cmi 
 library/declare.cmi: kernel/cooking.cmi kernel/declarations.cmi \
     kernel/environ.cmi kernel/indtypes.cmi library/libobject.cmi \
     library/library.cmi kernel/names.cmi library/nametab.cmi \
     kernel/safe_typing.cmi kernel/sign.cmi kernel/term.cmi kernel/univ.cmi 
-library/global.cmi: kernel/cooking.cmi kernel/declarations.cmi \
-    kernel/environ.cmi kernel/indtypes.cmi kernel/names.cmi \
-    library/nametab.cmi kernel/safe_typing.cmi kernel/sign.cmi \
-    kernel/term.cmi kernel/univ.cmi 
+library/global.cmi: kernel/declarations.cmi kernel/environ.cmi \
+    kernel/indtypes.cmi kernel/names.cmi library/nametab.cmi \
+    kernel/safe_typing.cmi kernel/sign.cmi kernel/term.cmi kernel/univ.cmi 
 library/goptions.cmi: kernel/names.cmi library/nametab.cmi lib/pp.cmi \
     kernel/term.cmi 
 library/impargs.cmi: kernel/environ.cmi kernel/names.cmi library/nametab.cmi \
@@ -46,8 +47,6 @@ library/nametab.cmi: kernel/environ.cmi kernel/names.cmi lib/pp.cmi \
 library/opaque.cmi: kernel/closure.cmi kernel/environ.cmi kernel/names.cmi \
     kernel/safe_typing.cmi 
 library/summary.cmi: kernel/names.cmi 
-lib/system.cmi: lib/pp.cmi 
-lib/util.cmi: lib/pp.cmi 
 parsing/ast.cmi: parsing/coqast.cmi lib/dyn.cmi kernel/names.cmi \
     parsing/pcoq.cmi lib/pp.cmi 
 parsing/astterm.cmi: parsing/coqast.cmi kernel/environ.cmi pretyping/evd.cmi \
@@ -225,18 +224,18 @@ toplevel/recordobj.cmi: library/nametab.cmi
 toplevel/searchisos.cmi: library/libobject.cmi kernel/names.cmi \
     kernel/term.cmi 
 toplevel/toplevel.cmi: parsing/pcoq.cmi lib/pp.cmi 
+toplevel/vernac.cmi: parsing/coqast.cmi parsing/pcoq.cmi 
 toplevel/vernacentries.cmi: kernel/environ.cmi pretyping/evd.cmi \
     kernel/names.cmi kernel/term.cmi toplevel/vernacinterp.cmi 
 toplevel/vernacinterp.cmi: parsing/coqast.cmi lib/dyn.cmi kernel/names.cmi \
     library/nametab.cmi proofs/proof_type.cmi 
-toplevel/vernac.cmi: parsing/coqast.cmi parsing/pcoq.cmi 
 contrib/correctness/past.cmi: parsing/coqast.cmi kernel/names.cmi \
     contrib/correctness/ptype.cmi kernel/term.cmi 
+contrib/correctness/pcic.cmi: contrib/correctness/past.cmi \
+    pretyping/rawterm.cmi 
 contrib/correctness/pcicenv.cmi: kernel/names.cmi \
     contrib/correctness/penv.cmi contrib/correctness/prename.cmi \
     kernel/sign.cmi kernel/term.cmi 
-contrib/correctness/pcic.cmi: contrib/correctness/past.cmi \
-    pretyping/rawterm.cmi 
 contrib/correctness/pdb.cmi: kernel/names.cmi contrib/correctness/past.cmi \
     contrib/correctness/ptype.cmi 
 contrib/correctness/peffect.cmi: kernel/names.cmi lib/pp.cmi 
@@ -419,37 +418,45 @@ lib/edit.cmo: lib/bstack.cmi lib/pp.cmi lib/util.cmi lib/edit.cmi
 lib/edit.cmx: lib/bstack.cmx lib/pp.cmx lib/util.cmx lib/edit.cmi 
 lib/explore.cmo: lib/explore.cmi 
 lib/explore.cmx: lib/explore.cmi 
-lib/gmapl.cmo: lib/gmap.cmi lib/util.cmi lib/gmapl.cmi 
-lib/gmapl.cmx: lib/gmap.cmx lib/util.cmx lib/gmapl.cmi 
 lib/gmap.cmo: lib/gmap.cmi 
 lib/gmap.cmx: lib/gmap.cmi 
+lib/gmapl.cmo: lib/gmap.cmi lib/util.cmi lib/gmapl.cmi 
+lib/gmapl.cmx: lib/gmap.cmx lib/util.cmx lib/gmapl.cmi 
 lib/gset.cmo: lib/gset.cmi 
 lib/gset.cmx: lib/gset.cmi 
 lib/hashcons.cmo: lib/hashcons.cmi 
 lib/hashcons.cmx: lib/hashcons.cmi 
 lib/options.cmo: lib/util.cmi lib/options.cmi 
 lib/options.cmx: lib/util.cmx lib/options.cmi 
-lib/pp_control.cmo: lib/pp_control.cmi 
-lib/pp_control.cmx: lib/pp_control.cmi 
 lib/pp.cmo: lib/pp_control.cmi lib/pp.cmi 
 lib/pp.cmx: lib/pp_control.cmx lib/pp.cmi 
+lib/pp_control.cmo: lib/pp_control.cmi 
+lib/pp_control.cmx: lib/pp_control.cmi 
 lib/predicate.cmo: lib/predicate.cmi 
 lib/predicate.cmx: lib/predicate.cmi 
 lib/profile.cmo: lib/profile.cmi 
 lib/profile.cmx: lib/profile.cmi 
-library/declare.cmo: kernel/cooking.cmi kernel/declarations.cmi \
-    kernel/environ.cmi library/global.cmi library/impargs.cmi \
-    kernel/indtypes.cmi kernel/inductive.cmi library/lib.cmi \
-    library/libobject.cmi library/library.cmi library/nameops.cmi \
-    kernel/names.cmi library/nametab.cmi lib/pp.cmi kernel/reduction.cmi \
+lib/stamps.cmo: lib/stamps.cmi 
+lib/stamps.cmx: lib/stamps.cmi 
+lib/system.cmo: config/coq_config.cmi lib/pp.cmi lib/util.cmi lib/system.cmi 
+lib/system.cmx: config/coq_config.cmx lib/pp.cmx lib/util.cmx lib/system.cmi 
+lib/tlm.cmo: lib/gmap.cmi lib/gset.cmi lib/tlm.cmi 
+lib/tlm.cmx: lib/gmap.cmx lib/gset.cmx lib/tlm.cmi 
+lib/util.cmo: lib/pp.cmi lib/util.cmi 
+lib/util.cmx: lib/pp.cmx lib/util.cmi 
+library/declare.cmo: kernel/declarations.cmi kernel/environ.cmi \
+    library/global.cmi library/impargs.cmi kernel/indtypes.cmi \
+    kernel/inductive.cmi library/lib.cmi library/libobject.cmi \
+    library/library.cmi library/nameops.cmi kernel/names.cmi \
+    library/nametab.cmi lib/pp.cmi kernel/reduction.cmi \
     kernel/safe_typing.cmi kernel/sign.cmi library/summary.cmi \
     kernel/term.cmi kernel/type_errors.cmi kernel/typeops.cmi kernel/univ.cmi \
     lib/util.cmi library/declare.cmi 
-library/declare.cmx: kernel/cooking.cmx kernel/declarations.cmx \
-    kernel/environ.cmx library/global.cmx library/impargs.cmx \
-    kernel/indtypes.cmx kernel/inductive.cmx library/lib.cmx \
-    library/libobject.cmx library/library.cmx library/nameops.cmx \
-    kernel/names.cmx library/nametab.cmx lib/pp.cmx kernel/reduction.cmx \
+library/declare.cmx: kernel/declarations.cmx kernel/environ.cmx \
+    library/global.cmx library/impargs.cmx kernel/indtypes.cmx \
+    kernel/inductive.cmx library/lib.cmx library/libobject.cmx \
+    library/library.cmx library/nameops.cmx kernel/names.cmx \
+    library/nametab.cmx lib/pp.cmx kernel/reduction.cmx \
     kernel/safe_typing.cmx kernel/sign.cmx library/summary.cmx \
     kernel/term.cmx kernel/type_errors.cmx kernel/typeops.cmx kernel/univ.cmx \
     lib/util.cmx library/declare.cmi 
@@ -519,14 +526,6 @@ library/summary.cmo: lib/dyn.cmi kernel/names.cmi lib/pp.cmi lib/util.cmi \
     library/summary.cmi 
 library/summary.cmx: lib/dyn.cmx kernel/names.cmx lib/pp.cmx lib/util.cmx \
     library/summary.cmi 
-lib/stamps.cmo: lib/stamps.cmi 
-lib/stamps.cmx: lib/stamps.cmi 
-lib/system.cmo: config/coq_config.cmi lib/pp.cmi lib/util.cmi lib/system.cmi 
-lib/system.cmx: config/coq_config.cmx lib/pp.cmx lib/util.cmx lib/system.cmi 
-lib/tlm.cmo: lib/gmap.cmi lib/gset.cmi lib/tlm.cmi 
-lib/tlm.cmx: lib/gmap.cmx lib/gset.cmx lib/tlm.cmi 
-lib/util.cmo: lib/pp.cmi lib/util.cmi 
-lib/util.cmx: lib/pp.cmx lib/util.cmi 
 parsing/ast.cmo: parsing/coqast.cmi lib/dyn.cmi kernel/names.cmi \
     parsing/pcoq.cmi lib/pp.cmi lib/util.cmi parsing/ast.cmi 
 parsing/ast.cmx: parsing/coqast.cmx lib/dyn.cmx kernel/names.cmx \
@@ -1116,15 +1115,15 @@ tactics/dn.cmx: lib/tlm.cmx tactics/dn.cmi
 tactics/eauto.cmo: tactics/auto.cmi proofs/clenv.cmi proofs/evar_refiner.cmi \
     lib/explore.cmi proofs/logic.cmi kernel/names.cmi pretyping/pattern.cmi \
     lib/pp.cmi proofs/proof_trees.cmi proofs/proof_type.cmi \
-    kernel/reduction.cmi kernel/sign.cmi proofs/tacmach.cmi \
-    tactics/tacticals.cmi tactics/tactics.cmi kernel/term.cmi \
-    pretyping/termops.cmi lib/util.cmi 
+    kernel/reduction.cmi parsing/search.cmi kernel/sign.cmi \
+    proofs/tacmach.cmi tactics/tacticals.cmi tactics/tactics.cmi \
+    kernel/term.cmi pretyping/termops.cmi lib/util.cmi 
 tactics/eauto.cmx: tactics/auto.cmx proofs/clenv.cmx proofs/evar_refiner.cmx \
     lib/explore.cmx proofs/logic.cmx kernel/names.cmx pretyping/pattern.cmx \
     lib/pp.cmx proofs/proof_trees.cmx proofs/proof_type.cmx \
-    kernel/reduction.cmx kernel/sign.cmx proofs/tacmach.cmx \
-    tactics/tacticals.cmx tactics/tactics.cmx kernel/term.cmx \
-    pretyping/termops.cmx lib/util.cmx 
+    kernel/reduction.cmx parsing/search.cmx kernel/sign.cmx \
+    proofs/tacmach.cmx tactics/tacticals.cmx tactics/tactics.cmx \
+    kernel/term.cmx pretyping/termops.cmx lib/util.cmx 
 tactics/elim.cmo: proofs/clenv.cmi library/declare.cmi kernel/environ.cmi \
     tactics/hiddentac.cmi tactics/hipattern.cmi pretyping/inductiveops.cmi \
     kernel/names.cmi library/nametab.cmi lib/pp.cmi proofs/proof_type.cmi \
@@ -1296,9 +1295,10 @@ tactics/tactics.cmo: parsing/astterm.cmi proofs/clenv.cmi kernel/closure.cmi \
     kernel/inductive.cmi pretyping/inductiveops.cmi proofs/logic.cmi \
     library/nameops.cmi kernel/names.cmi library/nametab.cmi \
     proofs/pfedit.cmi lib/pp.cmi proofs/proof_trees.cmi proofs/proof_type.cmi \
-    pretyping/reductionops.cmi kernel/sign.cmi proofs/tacinterp.cmi \
-    proofs/tacmach.cmi pretyping/tacred.cmi tactics/tacticals.cmi \
-    kernel/term.cmi pretyping/termops.cmi lib/util.cmi tactics/tactics.cmi 
+    pretyping/reductionops.cmi kernel/safe_typing.cmi kernel/sign.cmi \
+    proofs/tacinterp.cmi proofs/tacmach.cmi pretyping/tacred.cmi \
+    tactics/tacticals.cmi kernel/term.cmi pretyping/termops.cmi lib/util.cmi \
+    tactics/tactics.cmi 
 tactics/tactics.cmx: parsing/astterm.cmx proofs/clenv.cmx kernel/closure.cmx \
     parsing/coqlib.cmx kernel/declarations.cmx library/declare.cmx \
     kernel/environ.cmx proofs/evar_refiner.cmx pretyping/evd.cmx \
@@ -1306,9 +1306,10 @@ tactics/tactics.cmx: parsing/astterm.cmx proofs/clenv.cmx kernel/closure.cmx \
     kernel/inductive.cmx pretyping/inductiveops.cmx proofs/logic.cmx \
     library/nameops.cmx kernel/names.cmx library/nametab.cmx \
     proofs/pfedit.cmx lib/pp.cmx proofs/proof_trees.cmx proofs/proof_type.cmx \
-    pretyping/reductionops.cmx kernel/sign.cmx proofs/tacinterp.cmx \
-    proofs/tacmach.cmx pretyping/tacred.cmx tactics/tacticals.cmx \
-    kernel/term.cmx pretyping/termops.cmx lib/util.cmx tactics/tactics.cmi 
+    pretyping/reductionops.cmx kernel/safe_typing.cmx kernel/sign.cmx \
+    proofs/tacinterp.cmx proofs/tacmach.cmx pretyping/tacred.cmx \
+    tactics/tacticals.cmx kernel/term.cmx pretyping/termops.cmx lib/util.cmx \
+    tactics/tactics.cmi 
 tactics/tauto.cmo: parsing/ast.cmi parsing/coqast.cmi tactics/hipattern.cmi \
     kernel/names.cmi lib/pp.cmi proofs/proof_type.cmi proofs/tacinterp.cmi \
     proofs/tacmach.cmi tactics/tacticals.cmi tactics/tactics.cmi lib/util.cmi 
@@ -1333,12 +1334,12 @@ tactics/wcclausenv.cmx: proofs/clenv.cmx kernel/environ.cmx \
     proofs/proof_trees.cmx pretyping/reductionops.cmx kernel/sign.cmx \
     proofs/tacmach.cmx kernel/term.cmx pretyping/termops.cmx lib/util.cmx \
     tactics/wcclausenv.cmi 
-tools/coqdep_lexer.cmo: config/coq_config.cmi 
-tools/coqdep_lexer.cmx: config/coq_config.cmx 
-tools/coqdep.cmo: config/coq_config.cmi tools/coqdep_lexer.cmo 
-tools/coqdep.cmx: config/coq_config.cmx tools/coqdep_lexer.cmx 
 tools/coq_vo2xml.cmo: config/coq_config.cmi toplevel/usage.cmi 
 tools/coq_vo2xml.cmx: config/coq_config.cmx toplevel/usage.cmx 
+tools/coqdep.cmo: config/coq_config.cmi tools/coqdep_lexer.cmo 
+tools/coqdep.cmx: config/coq_config.cmx tools/coqdep_lexer.cmx 
+tools/coqdep_lexer.cmo: config/coq_config.cmi 
+tools/coqdep_lexer.cmx: config/coq_config.cmx 
 tools/gallina.cmo: tools/gallina_lexer.cmo 
 tools/gallina.cmx: tools/gallina_lexer.cmx 
 toplevel/class.cmo: pretyping/classops.cmi kernel/declarations.cmi \
@@ -1517,6 +1518,16 @@ toplevel/toplevel.cmx: parsing/ast.cmx toplevel/errors.cmx library/lib.cmx \
     toplevel/vernac.cmx toplevel/vernacinterp.cmx toplevel/toplevel.cmi 
 toplevel/usage.cmo: config/coq_config.cmi toplevel/usage.cmi 
 toplevel/usage.cmx: config/coq_config.cmx toplevel/usage.cmi 
+toplevel/vernac.cmo: parsing/ast.cmi parsing/coqast.cmi library/lib.cmi \
+    library/library.cmi library/nameops.cmi kernel/names.cmi lib/options.cmi \
+    parsing/pcoq.cmi lib/pp.cmi library/states.cmi lib/system.cmi \
+    pretyping/termops.cmi lib/util.cmi toplevel/vernacinterp.cmi \
+    toplevel/vernac.cmi 
+toplevel/vernac.cmx: parsing/ast.cmx parsing/coqast.cmx library/lib.cmx \
+    library/library.cmx library/nameops.cmx kernel/names.cmx lib/options.cmx \
+    parsing/pcoq.cmx lib/pp.cmx library/states.cmx lib/system.cmx \
+    pretyping/termops.cmx lib/util.cmx toplevel/vernacinterp.cmx \
+    toplevel/vernac.cmi 
 toplevel/vernacentries.cmo: parsing/ast.cmi parsing/astterm.cmi \
     toplevel/class.cmi pretyping/classops.cmi toplevel/command.cmi \
     parsing/coqast.cmi kernel/declarations.cmi library/declare.cmi \
@@ -1563,28 +1574,6 @@ toplevel/vernacinterp.cmx: parsing/ast.cmx parsing/astterm.cmx \
     kernel/names.cmx library/nametab.cmx lib/options.cmx lib/pp.cmx \
     proofs/proof_type.cmx proofs/tacinterp.cmx lib/util.cmx \
     toplevel/vernacinterp.cmi 
-toplevel/vernac.cmo: parsing/ast.cmi parsing/coqast.cmi library/lib.cmi \
-    library/library.cmi library/nameops.cmi kernel/names.cmi lib/options.cmi \
-    parsing/pcoq.cmi lib/pp.cmi library/states.cmi lib/system.cmi \
-    pretyping/termops.cmi lib/util.cmi toplevel/vernacinterp.cmi \
-    toplevel/vernac.cmi 
-toplevel/vernac.cmx: parsing/ast.cmx parsing/coqast.cmx library/lib.cmx \
-    library/library.cmx library/nameops.cmx kernel/names.cmx lib/options.cmx \
-    parsing/pcoq.cmx lib/pp.cmx library/states.cmx lib/system.cmx \
-    pretyping/termops.cmx lib/util.cmx toplevel/vernacinterp.cmx \
-    toplevel/vernac.cmi 
-contrib/correctness/pcicenv.cmo: library/global.cmi kernel/names.cmi \
-    contrib/correctness/past.cmi contrib/correctness/penv.cmi \
-    contrib/correctness/pmisc.cmi contrib/correctness/pmonad.cmi \
-    contrib/correctness/prename.cmi contrib/correctness/ptype.cmi \
-    contrib/correctness/putil.cmi kernel/sign.cmi kernel/term.cmi \
-    kernel/univ.cmi contrib/correctness/pcicenv.cmi 
-contrib/correctness/pcicenv.cmx: library/global.cmx kernel/names.cmx \
-    contrib/correctness/past.cmi contrib/correctness/penv.cmx \
-    contrib/correctness/pmisc.cmx contrib/correctness/pmonad.cmx \
-    contrib/correctness/prename.cmx contrib/correctness/ptype.cmi \
-    contrib/correctness/putil.cmx kernel/sign.cmx kernel/term.cmx \
-    kernel/univ.cmx contrib/correctness/pcicenv.cmi 
 contrib/correctness/pcic.cmo: parsing/ast.cmi kernel/declarations.cmi \
     library/declare.cmi pretyping/detyping.cmi kernel/indtypes.cmi \
     kernel/names.cmi library/nametab.cmi contrib/correctness/past.cmi \
@@ -1597,6 +1586,18 @@ contrib/correctness/pcic.cmx: parsing/ast.cmx kernel/declarations.cmx \
     contrib/correctness/pmisc.cmx pretyping/rawterm.cmx toplevel/record.cmx \
     kernel/sign.cmx kernel/term.cmx pretyping/termops.cmx kernel/typeops.cmx \
     lib/util.cmx contrib/correctness/pcic.cmi 
+contrib/correctness/pcicenv.cmo: library/global.cmi kernel/names.cmi \
+    contrib/correctness/past.cmi contrib/correctness/penv.cmi \
+    contrib/correctness/pmisc.cmi contrib/correctness/pmonad.cmi \
+    contrib/correctness/prename.cmi contrib/correctness/ptype.cmi \
+    contrib/correctness/putil.cmi kernel/sign.cmi kernel/term.cmi \
+    kernel/univ.cmi contrib/correctness/pcicenv.cmi 
+contrib/correctness/pcicenv.cmx: library/global.cmx kernel/names.cmx \
+    contrib/correctness/past.cmi contrib/correctness/penv.cmx \
+    contrib/correctness/pmisc.cmx contrib/correctness/pmonad.cmx \
+    contrib/correctness/prename.cmx contrib/correctness/ptype.cmi \
+    contrib/correctness/putil.cmx kernel/sign.cmx kernel/term.cmx \
+    kernel/univ.cmx contrib/correctness/pcicenv.cmi 
 contrib/correctness/pdb.cmo: library/declare.cmi library/global.cmi \
     kernel/names.cmi library/nametab.cmi contrib/correctness/past.cmi \
     contrib/correctness/peffect.cmi contrib/correctness/penv.cmi \
@@ -1711,8 +1712,8 @@ contrib/correctness/psyntax.cmo: parsing/ast.cmi parsing/astterm.cmi \
     contrib/correctness/pmonad.cmi lib/pp.cmi contrib/correctness/prename.cmi \
     contrib/correctness/ptactic.cmi contrib/correctness/ptype.cmi \
     contrib/correctness/ptyping.cmi contrib/correctness/putil.cmi \
-    kernel/reduction.cmi proofs/tacinterp.cmi kernel/term.cmi \
-    parsing/termast.cmi lib/util.cmi toplevel/vernac.cmi \
+    kernel/reduction.cmi kernel/safe_typing.cmi proofs/tacinterp.cmi \
+    kernel/term.cmi parsing/termast.cmi lib/util.cmi toplevel/vernac.cmi \
     toplevel/vernacentries.cmi toplevel/vernacinterp.cmi \
     contrib/correctness/psyntax.cmi 
 contrib/correctness/psyntax.cmx: parsing/ast.cmx parsing/astterm.cmx \
@@ -1725,8 +1726,8 @@ contrib/correctness/psyntax.cmx: parsing/ast.cmx parsing/astterm.cmx \
     contrib/correctness/pmonad.cmx lib/pp.cmx contrib/correctness/prename.cmx \
     contrib/correctness/ptactic.cmx contrib/correctness/ptype.cmi \
     contrib/correctness/ptyping.cmx contrib/correctness/putil.cmx \
-    kernel/reduction.cmx proofs/tacinterp.cmx kernel/term.cmx \
-    parsing/termast.cmx lib/util.cmx toplevel/vernac.cmx \
+    kernel/reduction.cmx kernel/safe_typing.cmx proofs/tacinterp.cmx \
+    kernel/term.cmx parsing/termast.cmx lib/util.cmx toplevel/vernac.cmx \
     toplevel/vernacentries.cmx toplevel/vernacinterp.cmx \
     contrib/correctness/psyntax.cmi 
 contrib/correctness/ptactic.cmo: library/declare.cmi tactics/equality.cmi \
@@ -2033,14 +2034,6 @@ contrib/interface/pbp.cmx: parsing/coqlib.cmx contrib/interface/ctast.cmx \
     kernel/reduction.cmx proofs/tacinterp.cmx proofs/tacmach.cmx \
     tactics/tacticals.cmx tactics/tactics.cmx kernel/term.cmx \
     pretyping/typing.cmx lib/util.cmx contrib/interface/pbp.cmi 
-contrib/interface/showproof_ct.cmo: contrib/interface/ascent.cmi \
-    parsing/esyntax.cmi library/global.cmi toplevel/metasyntax.cmi lib/pp.cmi \
-    parsing/printer.cmi contrib/interface/translate.cmi \
-    contrib/interface/vtp.cmi contrib/interface/xlate.cmi 
-contrib/interface/showproof_ct.cmx: contrib/interface/ascent.cmi \
-    parsing/esyntax.cmx library/global.cmx toplevel/metasyntax.cmx lib/pp.cmx \
-    parsing/printer.cmx contrib/interface/translate.cmx \
-    contrib/interface/vtp.cmx contrib/interface/xlate.cmx 
 contrib/interface/showproof.cmo: parsing/ast.cmi parsing/astterm.cmi \
     proofs/clenv.cmi parsing/coqast.cmi kernel/declarations.cmi \
     kernel/environ.cmi pretyping/evd.cmi library/global.cmi \
@@ -2061,6 +2054,14 @@ contrib/interface/showproof.cmx: parsing/ast.cmx parsing/astterm.cmx \
     kernel/term.cmx parsing/termast.cmx pretyping/termops.cmx \
     contrib/interface/translate.cmx pretyping/typing.cmx lib/util.cmx \
     toplevel/vernacinterp.cmx contrib/interface/showproof.cmi 
+contrib/interface/showproof_ct.cmo: contrib/interface/ascent.cmi \
+    parsing/esyntax.cmi library/global.cmi toplevel/metasyntax.cmi lib/pp.cmi \
+    parsing/printer.cmi contrib/interface/translate.cmi \
+    contrib/interface/vtp.cmi contrib/interface/xlate.cmi 
+contrib/interface/showproof_ct.cmx: contrib/interface/ascent.cmi \
+    parsing/esyntax.cmx library/global.cmx toplevel/metasyntax.cmx lib/pp.cmx \
+    parsing/printer.cmx contrib/interface/translate.cmx \
+    contrib/interface/vtp.cmx contrib/interface/xlate.cmx 
 contrib/interface/translate.cmo: contrib/interface/ascent.cmi parsing/ast.cmi \
     contrib/interface/ctast.cmo kernel/environ.cmi pretyping/evarutil.cmi \
     pretyping/evd.cmi library/libobject.cmi library/library.cmi \
@@ -2157,6 +2158,8 @@ contrib/romega/refl_omega.cmx: parsing/ast.cmx tactics/auto.cmx \
     parsing/printer.cmx proofs/proof_type.cmx kernel/reduction.cmx \
     kernel/sign.cmx proofs/tacmach.cmx tactics/tacticals.cmx \
     tactics/tactics.cmx kernel/term.cmx lib/util.cmx 
+contrib/xml/xml.cmo: contrib/xml/xml.cmi 
+contrib/xml/xml.cmx: contrib/xml/xml.cmi 
 contrib/xml/xmlcommand.cmo: kernel/declarations.cmi library/declare.cmi \
     kernel/environ.cmi pretyping/evd.cmi library/global.cmi library/lib.cmi \
     library/libobject.cmi library/library.cmi library/nameops.cmi \
@@ -2177,8 +2180,6 @@ contrib/xml/xmlentries.cmo: lib/util.cmi toplevel/vernacinterp.cmi \
     contrib/xml/xmlcommand.cmi 
 contrib/xml/xmlentries.cmx: lib/util.cmx toplevel/vernacinterp.cmx \
     contrib/xml/xmlcommand.cmx 
-contrib/xml/xml.cmo: contrib/xml/xml.cmi 
-contrib/xml/xml.cmx: contrib/xml/xml.cmi 
 tactics/tauto.cmo: parsing/grammar.cma kernel/names.cmo parsing/ast.cmo parsing/g_tactic.cmo parsing/g_ltac.cmo parsing/g_constr.cmo
 contrib/correctness/psyntax.cmo: parsing/grammar.cma
 contrib/field/field.cmo: parsing/grammar.cma kernel/names.cmo parsing/ast.cmo parsing/g_tactic.cmo parsing/g_ltac.cmo parsing/g_constr.cmo
diff --git a/.depend.coq b/.depend.coq
index 41dcf01809..ba5596bc7c 100644
--- a/.depend.coq
+++ b/.depend.coq
@@ -33,6 +33,9 @@ contrib/omega/Zpower.vo: contrib/omega/Zpower.v theories/ZArith/ZArith.vo contri
 contrib/omega/OmegaSyntax.vo: contrib/omega/OmegaSyntax.v
 contrib/omega/Zlogarithm.vo: contrib/omega/Zlogarithm.v theories/ZArith/ZArith.vo contrib/omega/Omega.vo contrib/omega/Zcomplements.vo contrib/omega/Zpower.vo
 contrib/omega/Omega.vo: contrib/omega/Omega.v theories/ZArith/ZArith.vo theories/Arith/Minus.vo contrib/omega/OmegaSyntax.vo
+theories/Sorting/Sorting.vo: theories/Sorting/Sorting.v theories/Lists/PolyList.vo theories/Sets/Multiset.vo theories/Sorting/Permutation.vo theories/Relations/Relations.vo
+theories/Sorting/Permutation.vo: theories/Sorting/Permutation.v theories/Relations/Relations.vo theories/Lists/PolyList.vo theories/Sets/Multiset.vo
+theories/Sorting/Heap.vo: theories/Sorting/Heap.v theories/Lists/PolyList.vo theories/Sets/Multiset.vo theories/Sorting/Permutation.vo theories/Relations/Relations.vo theories/Sorting/Sorting.vo
 theories/Setoids/Setoid.vo: theories/Setoids/Setoid.v
 theories/Reals/Reals.vo: theories/Reals/Reals.v theories/Reals/Rdefinitions.vo theories/Reals/TypeSyntax.vo theories/Reals/Raxioms.vo theories/Reals/Rbase.vo theories/Reals/R_Ifp.vo theories/Reals/Rbasic_fun.vo theories/Reals/Rlimit.vo theories/Reals/Rfunctions.vo theories/Reals/Rderiv.vo theories/Reals/Rseries.vo theories/Reals/Rtrigo_fun.vo
 theories/Reals/Rtrigo_fun.vo: theories/Reals/Rtrigo_fun.v theories/Reals/Rseries.vo
diff --git a/Makefile b/Makefile
index e34dd8a54b..52be6f90b5 100644
--- a/Makefile
+++ b/Makefile
@@ -387,6 +387,10 @@ ARITHVO=theories/Arith/Arith.vo         theories/Arith/Gt.vo          \
 	theories/Arith/Wf_nat.vo  	theories/Arith/Max.vo	      \
 #	theories/Arith/Div.vo 
 
+SORTINGVO=theories/Sorting/Heap.vo \
+	theories/Sorting/Permutation.vo \
+	theories/Sorting/Sorting.vo
+ 
 BOOLVO=theories/Bool/Bool.vo  		theories/Bool/IfProp.vo \
        theories/Bool/Zerob.vo 		theories/Bool/DecBool.vo \
 	theories/Bool/Sumbool.vo 	theories/Bool/BoolEq.vo
@@ -454,7 +458,7 @@ SETOIDSVO=theories/Setoids/Setoid.vo
 
 THEORIESVO = $(LOGICVO) $(ARITHVO) $(BOOLVO) $(ZARITHVO) $(LISTSVO) \
              $(SETSVO) $(INTMAPVO) $(RELATIONSVO) $(WELLFOUNDEDVO) \
-	     $(REALSVO) $(SETOIDSVO)
+	     $(REALSVO) $(SETOIDSVO) $(SORTINGVO)
 
 $(THEORIESVO): states/initial.coq
 
@@ -470,6 +474,7 @@ intmap: $(INTMAPVO)
 relations: $(RELATIONSVO)
 wellfounded: $(WELLFOUNDEDVO)
 reals: $(REALSVO)
+sorting: $(SORTING)
 
 clean::
 	rm -f theories/*/*.vo
diff --git a/contrib/extraction/test/.depend b/contrib/extraction/test/.depend
index 89ca9205c2..cb1cf8aa0c 100644
--- a/contrib/extraction/test/.depend
+++ b/contrib/extraction/test/.depend
@@ -20,20 +20,22 @@ theories/Arith/euclid.cmx: theories/Arith/compare_dec.cmx \
     theories/Init/specif.cmx theories/Arith/wf_nat.cmx 
 theories/Arith/even.cmo: theories/Init/datatypes.cmo theories/Init/specif.cmo 
 theories/Arith/even.cmx: theories/Init/datatypes.cmx theories/Init/specif.cmx 
-theories/Arith/min.cmo: theories/Init/datatypes.cmo 
-theories/Arith/min.cmx: theories/Init/datatypes.cmx 
+theories/Arith/max.cmo: theories/Init/datatypes.cmo theories/Init/specif.cmo 
+theories/Arith/max.cmx: theories/Init/datatypes.cmx theories/Init/specif.cmx 
+theories/Arith/min.cmo: theories/Init/datatypes.cmo theories/Init/specif.cmo 
+theories/Arith/min.cmx: theories/Init/datatypes.cmx theories/Init/specif.cmx 
 theories/Arith/minus.cmo: theories/Init/datatypes.cmo 
 theories/Arith/minus.cmx: theories/Init/datatypes.cmx 
+theories/Arith/mult.cmo: theories/Init/datatypes.cmo theories/Arith/plus.cmo 
+theories/Arith/mult.cmx: theories/Init/datatypes.cmx theories/Arith/plus.cmx 
 theories/Arith/peano_dec.cmo: theories/Init/datatypes.cmo \
     theories/Init/specif.cmo 
 theories/Arith/peano_dec.cmx: theories/Init/datatypes.cmx \
     theories/Init/specif.cmx 
 theories/Arith/plus.cmo: theories/Init/datatypes.cmo theories/Init/specif.cmo 
 theories/Arith/plus.cmx: theories/Init/datatypes.cmx theories/Init/specif.cmx 
-theories/Arith/wf_nat.cmo: theories/Init/datatypes.cmo \
-    theories/Init/specif.cmo theories/Init/wf.cmo 
-theories/Arith/wf_nat.cmx: theories/Init/datatypes.cmx \
-    theories/Init/specif.cmx theories/Init/wf.cmx 
+theories/Arith/wf_nat.cmo: theories/Init/datatypes.cmo theories/Init/wf.cmo 
+theories/Arith/wf_nat.cmx: theories/Init/datatypes.cmx theories/Init/wf.cmx 
 theories/Bool/bool.cmo: theories/Init/datatypes.cmo theories/Init/specif.cmo 
 theories/Bool/bool.cmx: theories/Init/datatypes.cmx theories/Init/specif.cmx 
 theories/Bool/boolEq.cmo: theories/Init/datatypes.cmo \
@@ -59,17 +61,15 @@ theories/Init/specif.cmx: theories/Init/datatypes.cmx
 theories/IntMap/adalloc.cmo: theories/IntMap/addec.cmo \
     theories/IntMap/addr.cmo theories/Init/datatypes.cmo \
     theories/ZArith/fast_integer.cmo theories/IntMap/map.cmo \
-    theories/Init/specif.cmo theories/Bool/sumbool.cmo 
+    theories/Init/specif.cmo 
 theories/IntMap/adalloc.cmx: theories/IntMap/addec.cmx \
     theories/IntMap/addr.cmx theories/Init/datatypes.cmx \
     theories/ZArith/fast_integer.cmx theories/IntMap/map.cmx \
-    theories/Init/specif.cmx theories/Bool/sumbool.cmx 
+    theories/Init/specif.cmx 
 theories/IntMap/addec.cmo: theories/IntMap/addr.cmo \
-    theories/Init/datatypes.cmo theories/ZArith/fast_integer.cmo \
-    theories/Init/specif.cmo theories/Bool/sumbool.cmo 
+    theories/Init/datatypes.cmo theories/ZArith/fast_integer.cmo 
 theories/IntMap/addec.cmx: theories/IntMap/addr.cmx \
-    theories/Init/datatypes.cmx theories/ZArith/fast_integer.cmx \
-    theories/Init/specif.cmx theories/Bool/sumbool.cmx 
+    theories/Init/datatypes.cmx theories/ZArith/fast_integer.cmx 
 theories/IntMap/addr.cmo: theories/Bool/bool.cmo theories/Init/datatypes.cmo \
     theories/ZArith/fast_integer.cmo theories/Init/specif.cmo 
 theories/IntMap/addr.cmx: theories/Bool/bool.cmx theories/Init/datatypes.cmx \
@@ -81,21 +81,17 @@ theories/IntMap/adist.cmx: theories/IntMap/addr.cmx \
     theories/Init/datatypes.cmx theories/ZArith/fast_integer.cmx \
     theories/Arith/min.cmx 
 theories/IntMap/fset.cmo: theories/IntMap/addec.cmo theories/IntMap/addr.cmo \
-    theories/Init/datatypes.cmo theories/IntMap/map.cmo \
-    theories/Init/specif.cmo 
+    theories/Init/datatypes.cmo theories/IntMap/map.cmo 
 theories/IntMap/fset.cmx: theories/IntMap/addec.cmx theories/IntMap/addr.cmx \
-    theories/Init/datatypes.cmx theories/IntMap/map.cmx \
-    theories/Init/specif.cmx 
+    theories/Init/datatypes.cmx theories/IntMap/map.cmx 
 theories/IntMap/lsort.cmo: theories/IntMap/addec.cmo theories/IntMap/addr.cmo \
-    theories/Bool/bool.cmo theories/Init/datatypes.cmo \
-    theories/ZArith/fast_integer.cmo theories/IntMap/mapiter.cmo \
-    theories/Lists/polyList.cmo theories/Init/specif.cmo \
-    theories/Bool/sumbool.cmo 
+    theories/Init/datatypes.cmo theories/ZArith/fast_integer.cmo \
+    theories/IntMap/mapiter.cmo theories/Lists/polyList.cmo \
+    theories/Init/specif.cmo 
 theories/IntMap/lsort.cmx: theories/IntMap/addec.cmx theories/IntMap/addr.cmx \
-    theories/Bool/bool.cmx theories/Init/datatypes.cmx \
-    theories/ZArith/fast_integer.cmx theories/IntMap/mapiter.cmx \
-    theories/Lists/polyList.cmx theories/Init/specif.cmx \
-    theories/Bool/sumbool.cmx 
+    theories/Init/datatypes.cmx theories/ZArith/fast_integer.cmx \
+    theories/IntMap/mapiter.cmx theories/Lists/polyList.cmx \
+    theories/Init/specif.cmx 
 theories/IntMap/map.cmo: theories/IntMap/addec.cmo theories/IntMap/addr.cmo \
     theories/Init/datatypes.cmo theories/ZArith/fast_integer.cmo \
     theories/Init/peano.cmo theories/Init/specif.cmo 
@@ -108,12 +104,12 @@ theories/IntMap/mapcard.cmo: theories/IntMap/addec.cmo \
     theories/IntMap/addr.cmo theories/Init/datatypes.cmo \
     theories/IntMap/map.cmo theories/Init/peano.cmo \
     theories/Arith/peano_dec.cmo theories/Arith/plus.cmo \
-    theories/Init/specif.cmo theories/Bool/sumbool.cmo 
+    theories/Init/specif.cmo 
 theories/IntMap/mapcard.cmx: theories/IntMap/addec.cmx \
     theories/IntMap/addr.cmx theories/Init/datatypes.cmx \
     theories/IntMap/map.cmx theories/Init/peano.cmx \
     theories/Arith/peano_dec.cmx theories/Arith/plus.cmx \
-    theories/Init/specif.cmx theories/Bool/sumbool.cmx 
+    theories/Init/specif.cmx 
 theories/IntMap/mapfold.cmo: theories/Init/datatypes.cmo \
     theories/IntMap/fset.cmo theories/IntMap/map.cmo \
     theories/IntMap/mapiter.cmo theories/Init/specif.cmo 
@@ -123,25 +119,25 @@ theories/IntMap/mapfold.cmx: theories/Init/datatypes.cmx \
 theories/IntMap/mapiter.cmo: theories/IntMap/addec.cmo \
     theories/IntMap/addr.cmo theories/Init/datatypes.cmo \
     theories/IntMap/map.cmo theories/Lists/polyList.cmo \
-    theories/Init/specif.cmo theories/Bool/sumbool.cmo 
+    theories/Init/specif.cmo 
 theories/IntMap/mapiter.cmx: theories/IntMap/addec.cmx \
     theories/IntMap/addr.cmx theories/Init/datatypes.cmx \
     theories/IntMap/map.cmx theories/Lists/polyList.cmx \
-    theories/Init/specif.cmx theories/Bool/sumbool.cmx 
+    theories/Init/specif.cmx 
 theories/IntMap/maplists.cmo: theories/IntMap/addec.cmo \
     theories/Init/datatypes.cmo theories/IntMap/map.cmo \
     theories/IntMap/mapiter.cmo theories/Lists/polyList.cmo \
-    theories/Init/specif.cmo theories/Bool/sumbool.cmo 
+    theories/Init/specif.cmo 
 theories/IntMap/maplists.cmx: theories/IntMap/addec.cmx \
     theories/Init/datatypes.cmx theories/IntMap/map.cmx \
     theories/IntMap/mapiter.cmx theories/Lists/polyList.cmx \
-    theories/Init/specif.cmx theories/Bool/sumbool.cmx 
-theories/IntMap/mapsubset.cmo: theories/Bool/bool.cmo \
-    theories/Init/datatypes.cmo theories/IntMap/fset.cmo \
-    theories/IntMap/map.cmo theories/IntMap/mapiter.cmo 
-theories/IntMap/mapsubset.cmx: theories/Bool/bool.cmx \
-    theories/Init/datatypes.cmx theories/IntMap/fset.cmx \
-    theories/IntMap/map.cmx theories/IntMap/mapiter.cmx 
+    theories/Init/specif.cmx 
+theories/IntMap/mapsubset.cmo: theories/Init/datatypes.cmo \
+    theories/IntMap/fset.cmo theories/IntMap/map.cmo \
+    theories/IntMap/mapiter.cmo 
+theories/IntMap/mapsubset.cmx: theories/Init/datatypes.cmx \
+    theories/IntMap/fset.cmx theories/IntMap/map.cmx \
+    theories/IntMap/mapiter.cmx 
 theories/Lists/listSet.cmo: theories/Init/datatypes.cmo \
     theories/Lists/polyList.cmo theories/Init/specif.cmo 
 theories/Lists/listSet.cmx: theories/Init/datatypes.cmx \
@@ -171,11 +167,9 @@ theories/Reals/raxioms.cmo: theories/Init/datatypes.cmo \
 theories/Reals/raxioms.cmx: theories/Init/datatypes.cmx \
     theories/ZArith/fast_integer.cmx 
 theories/Reals/rbase.cmo: theories/Reals/addReals.cmo \
-    theories/Init/specif.cmo theories/Reals/typeSyntax.cmo \
-    theories/ZArith/zarith_aux.cmo 
+    theories/Reals/typeSyntax.cmo theories/ZArith/zarith_aux.cmo 
 theories/Reals/rbase.cmx: theories/Reals/addReals.cmx \
-    theories/Init/specif.cmx theories/Reals/typeSyntax.cmx \
-    theories/ZArith/zarith_aux.cmx 
+    theories/Reals/typeSyntax.cmx theories/ZArith/zarith_aux.cmx 
 theories/Reals/rbasic_fun.cmo: theories/Reals/rbase.cmo \
     theories/Reals/typeSyntax.cmo 
 theories/Reals/rbasic_fun.cmx: theories/Reals/rbase.cmx \
@@ -200,6 +194,8 @@ theories/Relations/relation_Operators.cmx: theories/Lists/polyList.cmx \
     theories/Init/specif.cmx 
 theories/Sets/cpo.cmo: theories/Sets/partial_Order.cmo 
 theories/Sets/cpo.cmx: theories/Sets/partial_Order.cmx 
+theories/Sets/integers.cmo: theories/Sets/partial_Order.cmo 
+theories/Sets/integers.cmx: theories/Sets/partial_Order.cmx 
 theories/Sets/multiset.cmo: theories/Init/datatypes.cmo \
     theories/Init/peano.cmo theories/Init/specif.cmo 
 theories/Sets/multiset.cmx: theories/Init/datatypes.cmx \
@@ -210,6 +206,22 @@ theories/Sets/uniset.cmo: theories/Init/datatypes.cmo \
     theories/Init/specif.cmo 
 theories/Sets/uniset.cmx: theories/Init/datatypes.cmx \
     theories/Init/specif.cmx 
+theories/Sorting/heap.cmo: theories/Init/datatypes.cmo \
+    theories/Init/peano.cmo theories/Lists/polyList.cmo \
+    theories/Sorting/sorting.cmo theories/Init/specif.cmo 
+theories/Sorting/heap.cmx: theories/Init/datatypes.cmx \
+    theories/Init/peano.cmx theories/Lists/polyList.cmx \
+    theories/Sorting/sorting.cmx theories/Init/specif.cmx 
+theories/Sorting/permutation.cmo: theories/Init/datatypes.cmo \
+    theories/Init/peano.cmo theories/Lists/polyList.cmo \
+    theories/Init/specif.cmo 
+theories/Sorting/permutation.cmx: theories/Init/datatypes.cmx \
+    theories/Init/peano.cmx theories/Lists/polyList.cmx \
+    theories/Init/specif.cmx 
+theories/Sorting/sorting.cmo: theories/Lists/polyList.cmo \
+    theories/Init/specif.cmo 
+theories/Sorting/sorting.cmx: theories/Lists/polyList.cmx \
+    theories/Init/specif.cmx 
 theories/Wellfounded/well_Ordering.cmo: theories/Init/specif.cmo \
     theories/Init/wf.cmo 
 theories/Wellfounded/well_Ordering.cmx: theories/Init/specif.cmx \
@@ -219,15 +231,13 @@ theories/ZArith/fast_integer.cmo: theories/Init/datatypes.cmo \
 theories/ZArith/fast_integer.cmx: theories/Init/datatypes.cmx \
     theories/Init/peano.cmx 
 theories/ZArith/wf_Z.cmo: theories/Init/datatypes.cmo \
-    theories/ZArith/fast_integer.cmo theories/Init/peano.cmo \
-    theories/Init/specif.cmo 
+    theories/ZArith/fast_integer.cmo theories/Init/peano.cmo 
 theories/ZArith/wf_Z.cmx: theories/Init/datatypes.cmx \
-    theories/ZArith/fast_integer.cmx theories/Init/peano.cmx \
-    theories/Init/specif.cmx 
+    theories/ZArith/fast_integer.cmx theories/Init/peano.cmx 
 theories/ZArith/zArith_dec.cmo: theories/ZArith/fast_integer.cmo \
-    theories/Init/specif.cmo theories/Bool/sumbool.cmo 
+    theories/Init/specif.cmo 
 theories/ZArith/zArith_dec.cmx: theories/ZArith/fast_integer.cmx \
-    theories/Init/specif.cmx theories/Bool/sumbool.cmx 
+    theories/Init/specif.cmx 
 theories/ZArith/zarith_aux.cmo: theories/Init/datatypes.cmo \
     theories/ZArith/fast_integer.cmo 
 theories/ZArith/zarith_aux.cmx: theories/Init/datatypes.cmx \