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
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.
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.
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.
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.
Key merge with sorted keys