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:
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: