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 int
list → int list. This
is because OCaml’s comparison functions like <= (used
inside insert) work for types other than int. For example, OCaml knows how to
compare characters in alphabetical order:
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 n2. 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 n2. 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 log2n, and the same for the bottom half. So, the total work done is 2 × log2n × n, which is proportional to nlog2n.
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.