Talk:Merge algorithm
I would like to know if it is standard nomenclature to call "merge algorithms" the ones that follow.
- given a set of current account balances and a set of transactions, both sorted by account number, produce the set of new account balances after the transactions are applied; this requires always advancing the "new transactions" pointer in preference to the "account number" pointer when the two have equal keys, and adding all the numbers on either tape with the same account number to produce the new balance.
- produce a sorted list of records with keys present in all the lists (equijoin); this requires outputting a record whenever the keys of all the p0..n are equal.
- similarly for finding the largest number on one tape smaller than each number on another tape (e.g. to figure out what tax bracket each person is in).
- similarly for computing set differences: all the records in one list with no corresponding records in another.
I checked several books on algorithms and in all of them "merge algorithm" is taking two or more ordered lists and producing one ordered list in linear time. Maybe the above algorithms could be in another article.