Standard sorting functions in SML?

Question

Are there standard sorting functions in SML? The documentation on the Internet is so scarce I couldn't find any.

Answer 1

There is no sorting functionality defined in the SML Basis Library, but most implementations extend the basis library and add extra functionality.

As such MosML has both an ArraySort and a Listsort module, and SML/NJ has a LIST_SORT signature with a ListMergeSort implementation. It also features some other sorting features on arrays as MosML. See the toc of the SML/NJ Library Manual, for a full list.

Answer 2

As Jesper Reenberg points out, Standard ML compilers have each their own (non-standard, ironically) sorting libraries. Since the documentation for these lacks examples, here is how to sort a list of strings in ascending order using the various modules:

1. In SML/NJ and MLton, using the ListMergeSort.sort function:

   - fun sortStrings ss = ListMergeSort.sort (fn (s : string, t) => s > t) ss;
   [autoloading]
   [library $SMLNJ-LIB/Util/smlnj-lib.cm is stable]
   [autoloading done]
   val sortStrings = fn : string list -> string list
   - sortStrings ["World","Hello"];
   val it = ["Hello","World"] : string list
   

   The quirk with this library function is that it takes a "greater than" boolean predicate. Since Standard ML's > operator is overloaded, but defaults to int, I have to somehow explicitly annotate that I'm comparing strings.

2. In Moscow ML, using the Listsort.sort function:

   - load "Listsort";
   > val it = () : unit
   - fun sortStrings ss = Listsort.sort String.compare ss;
   > val sortStrings = fn : string list -> string list
   - sortStrings ["World", "Hello"];
   > val it = ["Hello", "World"] : string list
   

   The quirk with this library is that Moscow ML's interactive REPL does not auto-load Listsort. Typing load "Listsort"; is only necessary in the interactive REPL; when compiling programs, load is not used.

3. In Poly/ML, there is no library for sorting, so you have to define your own sorting function.

---

If neither of these sorting functions are sufficient, here is a number of other sorting functions written in Standard ML:

1. True QuickSort in Standard ML compares a naive QuickSort (that isn't really a QuickSort) with an implementation of Hoare's algorithm by John Coleman.

2. Rosetta Code's MergeSort in Standard ML:

   fun merge cmp ([], ys) = ys
     | merge cmp (xs, []) = xs
     | merge cmp (xs as x::xs', ys as y::ys') =
         case cmp (x, y) of
              GREATER => y :: merge cmp (xs, ys')
            | _       => x :: merge cmp (xs', ys)
   
   fun sort cmp [] = []
     | sort cmp [x] = [x]
     | sort cmp xs =
       let
         val ys = List.take (xs, length xs div 2)
         val zs = List.drop (xs, length xs div 2)
       in
         merge cmp (sort cmp ys, sort cmp zs)
       end