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