lib/mlton/basic/merge-sort.sig

   1 (* Copyright (C) 2009 Matthew Fluet.
   2  * Copyright (C) 1999-2006 Henry Cejtin, Matthew Fluet, Suresh
   3  *    Jagannathan, and Stephen Weeks.
   4  *
   5  * MLton is released under a BSD-style license.
   6  * See the file MLton-LICENSE for details.
   7  *)
   8
   9 signature MERGE_SORT =
  10    sig
  11       type 'a t
  12
  13       (* The comparison function ('a * 'a -> bool) for any of these should
  14        * always be the <= funtion, not just <.
  15        * This is necessary to handle duplicate elements.
  16        *)
  17       val make: ('a * 'a -> bool) -> {isSorted: 'a t -> bool,
  18                                       merge: 'a t * 'a t -> 'a t,
  19                                       sort: 'a t -> 'a t}
  20       val isSorted: 'a t * ('a * 'a -> bool) -> 'a t
  21       val merge: 'a t * 'a t * ('a * 'a -> bool) -> 'a t
  22       val sort: 'a t * ('a * 'a -> bool) -> 'a t
  23    end
  24
  25 functor TestMergeSort (S: MERGE_SORT) =
  26 struct
  27
  28 open S
  29
  30 val _ =
  31    Assert.assert
  32    ("TestMergeSort", fn () =>
  33     let
  34        fun check (l: int list): bool =
  35           List.insertionSort (l, op <=) = toList (sort (fromList l, op <=))
  36     in
  37        List.forall
  38        ([[],
  39          [1],
  40          [1,2],
  41          [1,2,3],
  42          [2,1,3],
  43          [1,2,3,4,5],
  44          [3,5,6,7,8,1,2,3,6,4]],
  45         check)
  46     end)
  47
  48 end