Accession Number:

AD0733487

Title:

A Linear List Merging Algorithm.

Descriptive Note:

Technical rept.,

Corporate Author:

CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Hopcroft,J. E.
• Ullman,J. D.

Report Date:

1971-11-01

Pagination or Media Count:

20.0

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

Descriptors:

• *COMPUTER PROGRAMMING
• ALGORITHMS
• SET THEORY
• SEQUENCES
• DATA PROCESSING EQUIPMENT
• COMPILERS

Subject Categories:

• Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE