Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. A Linear List Merging Algorithm

A Linear List Merging Algorithm

File(s)
TR71-111.pdf (468.31 KB)
Permanent Link(s)
https://hdl.handle.net/1813/10810
Collections
Computer Science Technical Reports
Author
Hopcroft, John E.
Ullman, Jeffrey D.
Abstract

A linear list merging algorithm and its analysis is presented. Starting with n lists, each containing a single element, the algorithm will execute an arbitrary sequence of requests to merge lists and to find 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.

Date Issued
2008-05-14T13:42:16Z
Keywords
merging lists
•
list merging algorithms
•
algorithm

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance