"A Density Control Algorithm for Doing Insertions and Deletions in a Sequentially Ordered File inn a Good Worst-Case Time"

Consider a file which arranges records in sequential order, and stores them with possible empty spaces in M consecutive pages of memory. We develop an insertion/deletion algorithm which runs in a worst-case time approximately proportional to log^2(M) divided by the page-size when the set of manipulated records has cardinality O(M).

(c) DAN E. WILLARD Department of Computer Science, State University of New York, Albany, New York 12222 1992 Academic Press, Inc. Link to research paper