Access Restriction

Author Ferguson, David E.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Item ♦ Gamma distribution function ♦ Merge sort ♦ String ♦ File ♦ Seek time
Abstract A fixed buffer allocation for merge-sorting is presented here which minimizes the number of input-output operations for a given order of merge. When sorting on movable arm disks, the number of seeks is equal to the number of input-output operations, and the seek time usually controls the sort time. First some standard terminology is introduced. Then the input buffer allocation method is described, followed by an analysis of the improvement to be expected over more conventional allocation. This analysis makes use of a particular distribution function. An analysis of a completely different distribution is given which yields similar results. This suggests that the results do not depend on a particular distribution function. An optimum output buffer size is also determined. It is concluded that this buffering allocation can significantly reduce the time of merge sorting on movable arm disks when the input data are not random, and that this output buffer allocation should be used whether the data is random or not.
Description Affiliation: Programmatics Incorporated, Los Angeles, CA (Ferguson, David E.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 14
Issue Number 7
Page Count 3
Starting Page 476
Ending Page 478

Open content in new tab

   Open content in new tab
Source: ACM Digital Library