*NEXT* **·**
*UP* **·**
*PREVIOUS* **·**
*CONTENTS* **·**
*INDEX*
##
Sorting lists

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.]

*NEXT* **·**
*UP* **·**
*PREVIOUS* **·**
*CONTENTS* **·**
*INDEX*