A Linear List Merging Algorithm.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1971
- Accession Number
- AD0733487
Entities
People
- J. D. Ullman
- J. E. Hopcroft
Organizations
- Department of Computer Science, Cornell University