Sorted Lists

Elements consist of 2 parts: KEY & DATA.

They are ordered according to the KEY part.

Example: in a telephone book, your name is the KEY, your phone number and address is the DATA.

There is a unique place for each element. Therefore, when INSERTing an element, we do not need to specify where to place it.

Warning: The DATA part does not affect the algorithms operating on sorted lists. For the sake of convenience, we will never mention the DATA part again explicitly.

All list operations are defined for sorted lists.

A list operation is safe on sorted lists if it preserves the fact that the list is sorted.

Split is safe: L = [3,9,21,55]. When we SPLIT L between 9 and 21, we get [3,9] and [21,55], both of which are sorted.