Editing Standard ML (section)

====Mergesort====
{{main|Merge sort}}

Here, the classic mergesort algorithm is implemented in three functions: split, merge and mergesort. Also note the absence of types, with the exception of the syntax {{code|lang=sml|op ::}} and {{code|lang=sml|[]}} which signify lists. This code will sort lists of any type, so long as a consistent ordering function {{code|cmp}} is defined. Using [[Hindley–Milner type inference]], the types of all variables can be inferred, even complicated types such as that of the function {{code|cmp}}.

'''Split'''

{{code|lang=sml|fun split}} is implemented with a [[State (computer science)|stateful]] closure which alternates between {{code|true}} and {{code|false}}, ignoring the input:

<syntaxhighlight lang="sml">
fun alternator {} = let val state = ref true
    in fn a => !state before state := not (!state) end

(* Split a list into near-halves which will either be the same length,
 * or the first will have one more element than the other.
 * Runs in O(n) time, where n = |xs|.
 *)
fun split xs = List.partition (alternator {}) xs
</syntaxhighlight>

'''Merge'''

Merge uses a local function loop for efficiency. The inner {{code|loop}} is defined in terms of cases: when both lists are non-empty ({{code|lang=sml|x :: xs}}) and when one list is empty ({{code|lang=sml|[]}}).

This function merges two sorted lists into one sorted list. Note how the accumulator {{code|acc}} is built backwards, then reversed before being returned. This is a common technique, since {{code|lang=sml|'a list}} is represented as a [[Linked list#Linked lists vs. dynamic_arrays|linked list]]; this technique requires more clock time, but the [[Asymptotic analysis#Applications|asymptotics]] are not worse.

<syntaxhighlight lang="sml">
(* Merge two ordered lists using the order cmp.
 * Pre: each list must already be ordered per cmp.
 * Runs in O(n) time, where n = |xs| + |ys|.
 *)
fun merge cmp (xs, []) = xs
  | merge cmp (xs, y :: ys) = let
    fun loop (a, acc) (xs, []) = List.revAppend (a :: acc, xs)
      | loop (a, acc) (xs, y :: ys) =
        if cmp (a, y)
        then loop (y, a :: acc) (ys, xs)
        else loop (a, y :: acc) (xs, ys)
    in
        loop (y, []) (ys, xs)
    end
</syntaxhighlight>

'''Mergesort'''

The main function:

<syntaxhighlight lang="sml">
fun ap f (x, y) = (f x, f y)

(* Sort a list in according to the given ordering operation cmp.
 * Runs in O(n log n) time, where n = |xs|.
 *)
fun mergesort cmp [] = []
  | mergesort cmp [x] = [x]
  | mergesort cmp xs = (merge cmp o ap (mergesort cmp) o split) xs
</syntaxhighlight>