Collating two sequences

Batch processing often leads to the need to merge two sequences of items based on a common key. For example you may need to selectively update a stored sequence to keep in line with an external source, inserting new items, deleting missing items and updating items which occur on both list. In these examples we merely generate an annotated merged squence. In use, the action on match, new and delete would depend on the application.
See Wikibook for some early work and a blog item on detecting missing values.

1. lookup

Loop through one list , lookup on the other. It is not possible to detect items in target which are not in source in this algorithm.

2. Recursive Merge

A recursive merge compares the keys of the first items in each list to decide if there is a match or miss in either sequence. The function then recusively merges the remainder of the sequence. This assumes that the sequences are in key order. Care is required over the cases where either or both lists are exhausted.

3. Terminal Merge

The recursive merge might be faster if both sequences were teminated with high-value keys so empty conditions dont need to be tested. This was a typical device used in batch processing. However the performance is actually worse not better.

4. Key Merge

Key-based merge iterates through the full set of keys in both source and target sequences using distinct-values, indexing into both sequences to see if the key is present on both or only one. The sequences dont have to be in key order. If the output is required in key order, the keys can be sorted first.

5. Sorted Key Merge

Key merge with sorted keys