A Linear List Merging Algorithm
John E. Hopcroft, Jeffrey David Ullman · Defense Technical Information Center (DTIC) · 2008
A linear list merging algorithm and its analysis is presented. Starting with n lists, each containing a single element, the algorithm executes an arbitary sequence of requests to merge lists and finds the name of the list currently containing a given element. If the length of the sequence of requests is bounded by a constant times n, then the execution time of the algorithm on a random access computer is bounded by a constant times n. (Author)