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.
Pablo.cl 02:04, 24 May 2004 (UTC)
The only reference I've found so far that calls set difference a merge algorithm is Kragen Sitaker. I think the nomenclature is misleading, and that the examples in italics above, and also the middle one I copy below, should be in a separate article, tentatively called Sorted list algorithms.
I copy form kragen-hacks
Some examples of merge algorithms:
- produce a single sorted list from multiple sorted lists. (This is the kind of merge used in mergesort.)
- produce the set union, set intersection, or set difference of two sorted lists. [Set intersection and set difference would be moved to Sorted list algorithms.]
- given a master file and an update file sorted in the same order, produce a new master file with all the updates applied.