In [[parallel computing]], [[Array data structure|array]]s of sorted values may be merged efficiently using an [[all nearest smaller values]] computation.<ref>{{citation|first1=Omer|last1=Berkman|first2=Baruch|last2=Schieber|first3=Uzi|last3=Vishkin|author3-link=Uzi Vishkin|title=Optimal double logarithmic parallel algorithms based on finding all nearest smaller values|journal=Journal of Algorithms|volume=14|pages=344–370|year=1993|issue=3|doi=10.1006/jagm.1993.1018}}.</ref>
==Uses==
Merge can also be used for a variety of other things:
* 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 [[record (computer science)|record]]s with keys present in all the lists (equijoin); this requires outputting a record whenever the keys of all the p<sub>0..n</sub> 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.
* insertion/update operations in [[index (search engine)|search engines]] to produce an [[inverted index]]
* merging plays a central role in [[Dijkstra]]'s [[functional programming]] technique for generating [[regular number]]s
