Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://doi.org/10.1007/BF00996816 below:

An efficient external sorting with minimal space requirement

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 log₂ N is also required.

This is a preview of subscription content, log in via an institution to check access.

Springer+ Basic

€34.99 /Month

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime

Price includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

1. C. A. R. Hoare, “Partition (Algorithm 63), Quicksort (Algorithm 64), and Find (Algorithm 65),”Comm. ACM 4(7):321–322, (July 1961).

   Google Scholar 

2. C. A. R. Hoare, “Quicksort,”Computer J. 5(4):10–15, (April 1962).

   Google Scholar 

3. E. Horowitz and S. Sahni,Fundamentals of Data Structures (Computer Science Press, Polomac, Maryland, 1976), pp. 347–350.

   Google Scholar 

4. D. E. Knuth,Sorting and Searching, The Art of Computer Programming 3 (Addison-Wesley, Reading, Mass., 1972).

   Google Scholar 

5. R. Loeser, “Some performance tests of “quicksort” and descendants,”Comm. ACM 17,3:142–152 (March 1974).

   Google Scholar 

6. R. Loeser, “Survey on Algorithms 34, 422, and Quicksort,”ACM Translations on Mathematical Software,2(3):290–299 (September 1976).

   Google Scholar 

7. D. Motzkin, “A Stable Quicksort,”Software-Practice and Experience,11:607–611 (1981).

   Google Scholar 

8. L. T. Pardo, “Stable Sorting and Merging with Optimal Space and Time Bounds,”Siam J. Comput.,6(2):351–371 (June 1977).

   Google Scholar 

9. P. O. Rotes, “An Algorithm for Merging Disk Files in Place,”Questions Informaticae,1:41–43 (September 1979).

   Google Scholar 

10. R. D. Scowen, “Quickersort (Algorithm 271),”Comm. ACM 8(11):669–670 (November 1965).

    Google Scholar 

11. R. Sedgewick, “Quicksort with equal keys,”Siam J. Comput.,6(2):240–267 (June 1977).

    Google Scholar 

12. R. Sedgewick, “The analysis of Quicksort programs,”Acta Informatica 7:327–355 (1977).

    Google Scholar 

13. R. C. Singleton, “An efficient algorithm for sorting with minimal storage (Algorithm 347),”Comm. ACM 12(3):185–187 (March 1969).

    Google Scholar 

14. M. N. van Emden, “Increasing the efficiency of quicksort (Algorithm 402),”Comm. ACM 13,11:693–694 (November 1970).

    Google Scholar 

Download references

1. Department of Computer Science, Western Michigan University, Kalamazoo, Michigan

   Dalia Motzkin & Christina L. Hansen

1. Dalia Motzkin
2. Christina L. Hansen

This work was partially supported by a fellowship and grant from Western Michigan University.

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

Download citation

• Received: 15 July 1982

• Revised: 15 January 1983

• Issue Date: December 1982

• DOI: https://doi.org/10.1007/BF00996816

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4