Back to Contents

# Sorting Things

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 it take?

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.

## Questions

1. In msort, we calculate the value of the expression length l / 2 twice. Modify msort to remove this inefficiency.

2. We know that take and drop can fail if called with incorrect arguments. Show that this is never the case in msort.

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

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

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

6. Combine the sort and insert functions into a single sort function.