Abstract
An efficient external sorting algorithm with minimal space requirement is presented in this article. The average number of passes over the data is approximately 1 +Ln(N + 1)/4B, whereN is the number of records in the file to be sorted, andB is the buffer size. The external storage requirement is only the file itself, no additional disk space is required. The internal storage requirement is four buffers: two for input, and two for output. The buffer size can be adjusted to the available memory space. A stack of size log2 N is also required.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
C. A. R. Hoare, “Partition (Algorithm 63), Quicksort (Algorithm 64), and Find (Algorithm 65),”Comm. ACM 4(7):321–322, (July 1961).
C. A. R. Hoare, “Quicksort,”Computer J. 5(4):10–15, (April 1962).
E. Horowitz and S. Sahni,Fundamentals of Data Structures (Computer Science Press, Polomac, Maryland, 1976), pp. 347–350.
D. E. Knuth,Sorting and Searching, The Art of Computer Programming 3 (Addison-Wesley, Reading, Mass., 1972).
R. Loeser, “Some performance tests of “quicksort” and descendants,”Comm. ACM 17,3:142–152 (March 1974).
R. Loeser, “Survey on Algorithms 34, 422, and Quicksort,”ACM Translations on Mathematical Software,2(3):290–299 (September 1976).
D. Motzkin, “A Stable Quicksort,”Software-Practice and Experience,11:607–611 (1981).
L. T. Pardo, “Stable Sorting and Merging with Optimal Space and Time Bounds,”Siam J. Comput.,6(2):351–371 (June 1977).
P. O. Rotes, “An Algorithm for Merging Disk Files in Place,”Questions Informaticae,1:41–43 (September 1979).
R. D. Scowen, “Quickersort (Algorithm 271),”Comm. ACM 8(11):669–670 (November 1965).
R. Sedgewick, “Quicksort with equal keys,”Siam J. Comput.,6(2):240–267 (June 1977).
R. Sedgewick, “The analysis of Quicksort programs,”Acta Informatica 7:327–355 (1977).
R. C. Singleton, “An efficient algorithm for sorting with minimal storage (Algorithm 347),”Comm. ACM 12(3):185–187 (March 1969).
M. N. van Emden, “Increasing the efficiency of quicksort (Algorithm 402),”Comm. ACM 13,11:693–694 (November 1970).
Author information
Authors and Affiliations
Additional information
This work was partially supported by a fellowship and grant from Western Michigan University.
Rights and permissions
About this article
Cite this article
Motzkin, D., Hansen, C.L. An efficient external sorting with minimal space requirement. International Journal of Computer and Information Sciences 11, 381–396 (1982). https://doi.org/10.1007/BF00996816
Received:
Revised:
Issue date:
DOI: https://doi.org/10.1007/BF00996816