Virtual Memory Behavior of Some Sorting Algorithms
- 1 July 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. SE-10 (4) , 422-431
- https://doi.org/10.1109/tse.1984.5010255
Abstract
Experimnental results are given about the performance of six sorting algorithms in a virtual memory based on the working set principle. With one exception, the algorithms are general internal sorting algorithms and not especially tuned for virtual memory. Algorithms are compared in terms of their time requirements, space requirements, and space-time integrals. The relative performances of the algorithms vary from one measure to the other. Especially in terms of a space-time integral, quicksort turns out to be the best algorithm, also in a working set virtual memory environment.Keywords
This publication has 8 references indexed in Scilit:
- Some Results on the Working Set Anomalies in Numerical ProgramsIEEE Transactions on Software Engineering, 1982
- Methodology and empirical results of program behaviour measurementsPublished by Association for Computing Machinery (ACM) ,1980
- Working Sets Past and PresentIEEE Transactions on Software Engineering, 1980
- Bibliography on paging and related topicsACM SIGOPS Operating Systems Review, 1978
- Anomalies with variable partition paging algorithmsCommunications of the ACM, 1978
- Sortieren bei virtuellem SpeicherComputing, 1977
- Sorting in a paging environmentCommunications of the ACM, 1970
- The working set model for program behaviorCommunications of the ACM, 1968