Lists often need to be in sorted order. How might we write a function
to sort a list of integers? Well, a list with zero elements is already
sorted. If we do not have an empty list, we must have a head and a tail.
What can we do with those? Well, we can sort the tail by a recursive
call to our `sort`

function. So, now we have the head, and an
already sorted list. Now, we just need to write a function to insert the
head in an already sorted list. We have reduced the problem to an easier
one.

Now we just need to write the `insert`

function. This
takes an element and an already-sorted list, and returns the list with
the element inserted in the right place:

Consider the evaluation of
`insert 3 [1; 1; 2; 3; 5; 9]`

:

Here is the whole evaluation of `sort [53; 9; 2; 6; 19]`

.
We have missed out the detail of each `insert`

operation.

Here’s the full program, known as *insertion sort*:

Notice that the type ** α list → α
list** rather than

`<=`

(used
inside `insert`

) work for types other than How long does our sorting function take to run if the list to be
sorted has *n* elements? Under
the assumption that our argument list is arbitrarily ordered rather than
sorted, each `insert`

operation takes time proportional to
*n* (the element might need to
be inserted anywhere). We must run the `insert`

function as
many times as there are elements so, adding these all up, the
`sort`

function takes time proportional to *n*^{2}. You might argue that
the first `insert`

operations only have to work with a very
small list, and that this fact should make the time less that *n*^{2}. Can you see why that
is not true? What happens if the list is sorted already?

A more efficient algorithm can be found by considering a basic
operation a little more complex than `insert`

, but which
still operates in time proportional to the length of the argument list.
Such a function is `merge`

, which takes two already sorted
lists, and returns a single sorted list:

When `x`

and `y`

are both the empty list, the
first case is picked because `l`

matches the empty list. Here
is how `merge`

proceeds:

So merge can take two sorted lists, and produce a longer, sorted
list, containing all the elements from both lists. So, how can we use
this to sort a list from scratch? Well, we can use `length`

,
`take`

, and `drop`

from the previous chapter to
split the list into two halves. Now, we must use a recursive call to
sort each half, and then we can merge them. This is known as *merge
sort*.

The case for the single element is required because, if we split it into two halves, of length one and zero, the recursion would not end – we would not have reduced the size of the problem.

How does `msort`

work? Consider the evaluation of
`msort`

on the list `[53; 9; 2; 6; 19]`

. We will
skip the evaluation of the `merge`

, `drop`

,
`take`

, and `length`

functions, concentrating just
on `msort`

:

From now on we will not be showing these full evaluations all the time – but when you are unsure of how or why a function works, you can always write them out on paper yourself.

How long does merge sort take to run? We can visualize it with the following diagram, in which we have chosen a list of length eight (a power of two) for convenience.

`[6; 4; 5; 7; 2; 5; 3; 4]`

`[6; 4; 5; 7][2; 5; 3; 4]`

`[6; 4][5; 7][2; 5][3; 4]`

`[6][4][5][7][2][5][3][4]`

`[4; 6][5; 7][2; 5][3; 4]`

`[4; 5; 6; 7][2; 3; 4; 5]`

`[2; 3; 4; 4; 5; 5; 6; 7]`

In the top half of the diagram, the lists are being taken apart using
`take`

and `drop`

, until they are small enough to
already be sorted. In the bottom half, they are being merged back
together.

How long does each row take? For the top half: to split a list into
two halves takes time proportional to the length of the list. On the
first line, we do this once on a list of length eight. On the second
line, we do it twice on lists of length four, and so on. So each line
takes the same time overall. For the bottom half, we have another
function which takes time proportional to the length of its argument –
`merge`

– so each line in the bottom half takes time
proportional to the length too.

So, how many lines do we have? Well, in the top half we have roughly
log_{2}*n*, and the same
for the bottom half. So, the total work done is 2 × log_{2}*n* × *n*,
which is proportional to *n*log_{2}*n*.

In

`msort`

, we calculate the value of the expression`length l / 2`

twice. Modify`msort`

to remove this inefficiency.We know that

`take`

and`drop`

can fail if called with incorrect arguments. Show that this is never the case in`msort`

.Write a version of insertion sort which sorts the argument list into reverse order.

Write a function to detect if a list is already in sorted order.

We mentioned that the comparison functions like

`<`

work for many OCaml types. Can you determine, by experimentation, how they work for lists? For example, what is the result of`[1; 2] < [2; 3]`

? What happens when we sort the following list of type**char list list**? Why?`[[’o’; ’n’; ’e’]; [’t’; ’w’; ’o’]; [’t’; ’h’; ’r’; ’e’; ’e’]]`

Combine the

`sort`

and`insert`

functions into a single`sort`

function.