Insertion sort (Standard ML)
- Other implementations: ACL2 | C | C, simple | Erlang | Forth | Haskell | Java | OCaml | Standard ML | Visual Basic .NET
This is a simple example of the insertion sort sorting algorithm, written in Standard ML. Standard ML offers both mutable and immutable data-structures, so we will show an imperative implementation to sort an array in-place and a functional implementation to sort a list.
We will sort the data of type
'a with a comparator function
cmp : 'a * 'a -> order.
 Sorting in place
When sorting an array with insertion sort, we conceptually separate it into two parts:
- The array of elements already inserted, which is always in sorted order and is found at the beginning of the array;
- The array of elements we have yet to insert, following.
In outline, our primary function looks like this:
<<insertion_sort_mutable.sml>>= fun insertion_sort cmp a = Array.appi (fn (i, v) => ) a
Here, the index
i represents both the index of the next element to insert and the length of the sorted sublist constructed so far.
To insert each element, we need to create a hole in the array at the place where the element belongs, then place the element in that hole. We can combine the creation of the hole with the searching for the place by starting at the end and shifting each element up by one until we find the place where the element belongs. This overwrites the element we're inserting, so we have to save it in a variable first:
<<insert v into sorted sublist>>= (* Insert v into the sorted sublist *) let val j = ref (i - 1) in while !j >= 0 andalso cmp (Array.sub (a, !j), v) = GREATER do ( Array.update (a, !j + 1, Array.sub (a, !j)); j := !j - 1 ); Array.update (a, !j + 1, v) end
You must be aware that the average and worse case time complexity of
insertion_sort a are O(N2) where N =
Array.length a hence it is not recommended in practice (use a O(NlogN) algorithm instead).
There are several ways to compile sml code but for testing we recommend you to use the interactive toplevel
sml (in SML/NJ the
- is the prompt and start the lines you type in, the other lines are the answers of the system):
- val a = Array.fromList [5, 3, 1]; val a = [|5,3,1|] : int array - insertion_sort Int.compare a; val it = () : unit - a; val it = [|1,3,5|] : int array
 Sorting immutable lists
As above, we will make a function
insertion_sort : ('a * 'a -> order) -> 'a list -> 'a list that will take a comparator function
cmp and a list and return the list sorted.
The empty list
 is already sorted:
<<insertion_sort_immutable.sml>>= fun insertion_sort _  = 
If the list is not empty it consists of a first element
x followed by the remaining part of the list
xs. We sort
xs and insert
x at the right place:
<<insertion_sort_immutable.sml>>= | insertion_sort cmp (x::xs) = insert cmp x (insertion_sort cmp xs)
It remains to write
insert. Again, this is done by recursing on the list. Inserting an element
x into the empty list is easy:
<<insertion_sort_immutable.sml>>= and insert _ x  = [x]
If the list is made of a first element
y and a tail
ys, one has to check whether
x is greater than
y. In this case is must be inserted later in the list. Otherwise, it is the first element of the new list.
<<insertion_sort_immutable.sml>>= | insert cmp x (l as y::ys) = case cmp (x, y) of GREATER => y :: insert cmp x ys | _ => x :: l
As before we use the toplevel to interactively test our code:
- insertion_sort Int.compare [5, 3, 1]; val it = [1,3,5] : int list - insertion_sort String.compare ["bob", "alice", "zoe", "barry"]; val it = ["alice","barry","bob","zoe"] : string list
 Automated testing
To automatically test our function, we need to create a function that tests if a list is in order:
<<is_ordered predicate>>= fun is_ordered _  = true | is_ordered _ [y] = true | is_ordered cmp (y::ys) = is_ordered cmp ys andalso cmp(y, hd ys) <> GREATER
Conceptually, this says that a list of zero or one elements is always in order, and a list with two or more elements is in order if:
- The tail of the list is in order; and
- The first element of the list is less than or equal to the second element of the list.
Next we need to generate some input data. We can use the Random structure for this:
<<random list generator>>= fun random_list _ 0 =  | random_list r n = (Random.randInt(r))::(random_list r (n-1))
Finally, we sort some random lists and make sure the results are ordered, using a fixed seed for the random number generator, for reproducibility of any issues:
<<run tests immutable>>= let val r = Random.rand(12,35) val cmp = Int.compare fun test n = is_ordered cmp (insertion_sort cmp (random_list r n)) in if test 1 andalso test 100 andalso test 10000 then print "Success\n" else print "Error\n" end
For the mutable version, we need to convert our list to an array before sorting, and back to a list after sorting. The Array structure provides fromList, but we need to define toList. One simple way to do this is to take the list constructor
op:: and fold it over the array from right to left:
<<array to list>>= Array.foldr op::  array
Additionally, because the mutable version does not return a sorted array but rather modifies the array in place, we must use the semicolon (;) operator build an imperative sequence:
<<test mutable>>= let val a = Array.fromList (random_list r n) in (insertion_sort cmp a; is_ordered cmp (toList a)) end
The test is otherwise similar to the immutable version's test:
<<run tests mutable>>= let val r = Random.rand(12,35) val cmp = Int.compare fun toList array = fun test n = in if test 1 andalso test 100 andalso test 10000 then print "Success\n" else print "Error\n" end
We can then add these tests to the end of both implementations:
When we then run
sml on each file, it prints "Success".