The sorting routine which we will develop is simple insertion sort. There are two parts to this algorithm. The first is inserting an element into a sorted list in order to maintain the ordering; the second is repeatedly applying the insertion function.
Inserting an element into a sorted list has a simple base case where the empty list gives us a singleton (one-element) list. All singleton lists are sorted. For non-empty lists we compare the new element with the head. If the new element is smaller it is placed at the front. If larger, it is inserted into the tail.
fun insert (x, []) = [x]
| insert (x, h::t) =
if x <= h then x :: h :: t else h :: insert (x, t);This function has type int * int list -> int list, due to default overloading resolving the use of `<=' to take integer operands. Notice the inconvenience of having to reconstruct the list in the expression x :: h :: t after deconstructing it by pattern matching. We could bind the non-empty list to a single variable, say l, and then use let .. in .. end to destruct it, binding h and t as before but the as keyword does this much more conveniently. The following implementation is equivalent to the previous one.
fun insert (x, []) = [x]
| insert (x, l as h::t) =
if x <= h then x :: l else h :: insert (x, t);To sort a list we need only keep inserting the head element into the sorted tail. All empty lists are sorted.
fun sort [] = [] | sort (h::t) = insert (h, sort t);
Exercise
Implement the Quicksort algorithm due to C.A.R. Hoare. [You may find it useful to use the filter function from an earlier exercise.]