A Simple Optimal Randomized Algorithm for Sorting on the PDM

1. Aggarwal, A., Plaxton, G.: Optimal parallel sorting in multi-level storage. In: Proc of the ACM-SIAM SODA 1994, pp. 659–668 (1994)

   Google Scholar 

2. Aggarwal, A., Vitter, J.S.: The Input/Output Complexity of Sorting and Related Problems. Communications of the ACM 31(9), 1116–1127 (1988)

   Article  MathSciNet  Google Scholar 

3. Arge, L.: The Buffer Tree: A New Technique for Optimal I/O-Algorithms. In: Sack, J.-R., Akl, S.G., Dehne, F., Santoro, N. (eds.) WADS 1995. LNCS, vol. 955, pp. 334–345. Springer, Heidelberg (1995)

   Google Scholar 

4. Arge, L., Ferragina, P., Grossi, R., Vitter, J.S.: On Sorting Strings in External Memory. In: Proc. ACM Symposium on Theory of Computing (1995)

   Google Scholar 

5. Arge, L., Knudsen, M., Larsen, K.: A General Lower Bound on the I/O-Complexity of Comparison-based Algorithms. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1993. LNCS, vol. 709. Springer, Heidelberg (1993)

   Google Scholar 

6. Barve, R., Grove, E.F., Vitter, J.S.: Simple Randomized Mergesort on Parallel Disks. Parallel Computing 23(4-5), 601–631 (1997)

   Article  MATH  MathSciNet  Google Scholar 

7. Batcher, K.: Sorting Networks and their Applications. In: Proc. AFIPS Spring Joint Computing Conference, vol. 32, pp. 307–314 (1968)

   Google Scholar 

8. Chaudhry, G., Cormen, T.H.: Getting More From Out-of-Core Columnsort. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol. 2409, pp. 143–154. Springer, Heidelberg (2002)

   Chapter  Google Scholar 

9. Chaudhry, G., Cormen, T.H., Hamon, E.A.: Parallel Out-of-Core Sorting: The Third Way. To appear in Cluster Computing

   Google Scholar 

10. Chaudhry, G., Cormen, T.H., Wisniewski, L.F.: Columnsort Lives! An Efficient Out-of-Core Sorting Program. In: Proc. 13th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 169–178 (2001)

    Google Scholar 

11. Dementiev, R., Sanders, P.: Asynchronous Parallel Disk Sorting. In: Proc. ACM Symposium on Parallel Algorithms and Architectures, pp. 138–148 (2003)

    Google Scholar 

12. Horowitz, E., Sahni, S., Rajasekaran, S.: Computer Algorithms. W.H. Freeman, New York (1998)

    Google Scholar 

13. Hutchinson, D., Sanders, P., Vitter, J.: Duality between prefetching and queued writing with parallel disks. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 62–73. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

14. Leighton, T.: Tight Bounds on the Complexity of Parallel Sorting. IEEE Transactions on Computers C34(4), 344–354 (1985)

    Article  MATH  MathSciNet  Google Scholar 

15. Nodine, M., Vitter, J.: Deterministic distribution sort in shared and distributed memory multirocessors. In: Proc. of the ACM SPAA 1993, pp. 120–129 (1993)

    Google Scholar 

16. Nodine, M.H., Vitter, J.S.: Greed Sort: Optimal Deterministic Sorting on Parallel Disks. Journal of the ACM 42(4), 919–933 (1995)

    Article  MathSciNet  Google Scholar 

17. Rajasekaran, S.: Sorting and selection on interconnection networks. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 21, pp. 275–296 (1995)

    Google Scholar 

18. Rajasekaran, S.: A Framework for Simple Sorting Algorithms on Parallel Disk Systems. Theory of Computing Systems 34(2), 101–114 (2001)

    Article  MATH  MathSciNet  Google Scholar 

19. Rajasekaran, S., Sen, S.: PDM Sorting Algorithms That Take A Small Number of Passes (manuscript 2004)

    Google Scholar 

20. Sanders, P., Enger, S., Korst, J.: Fast concurrent access to parallel disks. In: Proc. of the ACM-SIAM SODA 2000, pp. 849–858 (2000)

    Google Scholar 

21. Thompson, C.D., Kung, H.T.: Sorting on a Mesh Connected Parallel Computer. Communications of the ACM 20(4), 263–271 (1977)

    Article  MATH  MathSciNet  Google Scholar 

22. Vitter, J.S., Hutchinson, D.A.: Distribution Sort with Randomized Cycling. In: Proc. 12th Annual SIAM/ACM Symposium on Discrete Algorithms (2001)

    Google Scholar 

23. Vitter, J.S., Shriver, E.A.M.: Algorithms for Parallel Memory I: Two-Level Memories. Algorithmica 12(2-3), 110–147 (1994)

    Article  MATH  MathSciNet  Google Scholar 

Download references