A sorted list is a list that has a special property; its elements are ordered according to their value. To be more precise, the elements of a sorted list are generally considered to have two parts:

- the KEY part
- the DATA part

Note that in a sorted list there is a unique place for each
element. This simple property is extremely important. For example, it
means that when we INSERT an element into a sorted list, we do not
have to specify *where* to place it - its position is uniquely
determined by the elements already in the list. This is not true of
ordinary lists, where we have to explicitly say where to place a new
element.

In the examples that I will do in the lectures about sorted lists, I will assume that the elements are in ascending order. Of course, the same discussion and algorithms apply if the elements are in decreasing order. I will also assume that no two elements in a list have the same key. Again, this does not affect the algorithms in any significant way: they just have to be extended with some mechanism for coping with distinct values with equal keys. Finally, it will be convenient to ignore the data part of the elements. This part of the elements is, of course, extremely significant in the application. But it is irrelevant to the operations that create, access, and update sorted lists; and those are the operations we'll be discussing. I won't even bother to draw the DATA part, but you should remember that there is one that is carried along wherever the KEY part goes.

A sorted list, then, is a list, and therefore all the ordinary list
operations are defined for sorted lists. We say that a list operation
is *safe* for sorted lists, if the operation *preserves*
the fact that the list is sorted.

For example, consider the operation SPLIT. Is it is a safe operation? Let's see, suppose we have a sorted list, e.g. L = [3,9,21,55] Wherever we split L, the two lists we get are both sorted. e.g. split L between 9 and 21, you get [3,9] and [21,55].

This is not a fluke of this example: SPLIT is safe for sorted lists.

What about the JOIN operation? Well, what happens if we join the
two lists from the previous example? They are sorted lists, and they
return the original L, which is also sorted. This *is* a fluke
of the example, but it is important - we will examine it closely
later. For now, here's an example showing that JOIN is not safe. Take
the two lists: L1 = [11,99] and L2 = [2,111,222]. When we JOIN these,
we get a list that is not sorted.

There is a natural way to combine two sorted lists, L1 and L2, so
that the result is always sorted. In fact, there is a *unique safe*
way to combine them: this follows from the fact that there is a unique
place in L1 for each element in L2. The operation that safely combines
two sorted lists is called MERGE. Its specification is:

- Inputs: L1, L2 (lists).
- Output: L3 (a list).
- Precondition: L1 and L2 are sorted.
- Postcondition: L3 is sorted and contains all the elements of L1 and L2 and no other elements.