Cited By
View all- Bahig HDaoud S(2005)Practical integer sorting on shared memoryProceedings of the First international conference on High Performance Computing and Communications10.1007/11557654_33(271-276)Online publication date: 21-Sep-2005
Parallel Self-Index Integer Sorting
Pages 269 - 275
Abstract
We consider the problem of sorting n integers when the elements are drawn from the restricted domain [1… n ]. A new deterministic parallel algorithm for sorting n integers is obtained. Its running time is O(log n log( n /log n )) using n /log n processors on EREW (exclusive read exclusive write) PRAM (parallel random access machine). Also, our algorithm was modified to become optimal when we use \sqrt{n} processors. This algorithm belongs to class EP (Efficient, Polynomial fast).
References
[1]
1. S. Albers and T. Hagerup. Improved integer sorting without concurrent writing. Information and Computation , 136:25-51, 1997.
[2]
2. H. Bast and T. Hagerup. Fast parallel space allocation, estimation, and integer sorting. Information and Computation , 123:72-110, 1995.
[3]
3. P. C. P. Bhatt, K. Diks, T. Hagerup, V. C. Prasad, T. Radzik, and S. Saxena. Improved deterministic parallel integer sorting. Information and Computation , 94:29-47, 1991.
[4]
4. B. Chlebus. A parallel bucket sort. Information Processing Letters , 27:57-61, 1988.
[5]
5. R. Cole. Parallel merge sort. SIAM Journal of Computing , 17:770-785, 1988.
[6]
6. A. Dessmark and A. Lingas. Improved bounds for integer sorting in the EREW PRASM model. Parallel and Distributed Computing , 48:64-70, 1998.
[7]
7. T. Hagerup. Towards optimal parallel bucket sorting. Information and Computation , 75:39-51, 1987.
[8]
8. R. Karp and V. Ramachandran. Parallel algorithms for shared-memory machines. In Handbook of Theoretical Computer Science , vol. A, pp. 870-941. Elsevier Science Publisher, North Holland, Amsterdam, 1990.
[9]
9. D. Knuth. The Art of Computer Programming: Sorting and Searching , pp. 75-85. Addison-Wesley, Reading, MA, 1973.
[10]
10. C. Kruskal, L. Rudolph, and M. Snir. Efficient parallel algorithms for graph problems. Algorithmica , 5:43-64, 1990.
[11]
11. C. Kruskal, L. Rudolph, and M. Snir. A complexity theory of efficient parallel algorithms. In Handbook of Theoretical Computer Science , vol. 7, pp. 95-132, 1990.
[12]
12. P. MacKenzie and Q. Stout. Ultra-fast expected time parallel algorithms. In Proceedings of the Symposium on Discrete Algorithms , pp. 414-423, 1991.
[13]
13. Y. Matias and U. Vishkin. On parallel hashing and integer sorting. In Proceedings of the 17th ICALP , Springer LNCS 443, pp. 729-743, 1990.
[14]
14. P. Ragde. The simplicity of compaction and chaining. In Proceedings of the 17th ICALP , Springer LNCS 443, pp. 744-751, 1990.
[15]
15. S. Rajasekaran and J. H. Reif. Optimal and sublogarithmic time randomized parallel sorting algorithms. SIAM Journal of Computing , 18:594-607, 1989.
[16]
16. S. Rajasekaran and S. Sen. On parallel integer sorting. Acta Informatica , 29:1-19, 1992.
[17]
17. R. Raman. The power of collision: Randomized parallel algorithm for chaining and integer sorting. In Proceedings of the 10th Conference on Foundation Software Technology and Theoretical Computer Science , LNCS vol. 472, pp. 161-175, 1990.
[18]
18. R. Raman. Optimal sub-logarithmic time integer sorting on the CRCW PRAM. Technical report no. 370. Computer Science Department, University of Rochester, New York, January 1991.
[19]
19. J. H. Reif. An optimal parallel algorithm for integer sorting. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing , pp. 496-504, 1984.
[20]
20. S. Saxena. Parallel integer sorting and simulation amongst CRCW models. Acta Informatica , 33(7):607-619, 1996.
[21]
21. R. Vaidyanathan, C. Hartmann, and P. Varshney. Parallel integer sorting using small operations. Acta Informatica , 32(1):79-92, 1995.
[22]
22. R. Wagner and Y. Han. Parallel algorithms for bucket sorting and the data dependent prefix problem. In Proceedings of the International Conference on Parallel Processing , pp. 924-930. Illinois, 1986.
[23]
23. S. Wang. A new sort algorithm: Self-index sort. ACM SIGPLAN Notices , 31(3):28-36, 1996.
Index Terms
- Parallel Self-Index Integer Sorting
Recommendations
A note on reducing parallel model simulations to integer sorting
IPPS '95: Proceedings of the 9th International Symposium on Parallel ProcessingWe show that simulating a step of a FETCH&ADD PRAM model on an EREW PRAM model can be made as efficient as integer sorting. In particular, we present several efficient reductions of the simulation problem to various integer sorting problems. By using ...
Parallel Integer Sorting Is More Efficient Than Parallel Comparison Sorting on Exclusive Write PRAMs
We present a significant improvement for parallel integer sorting. On the EREW (exclusive read exclusive write) PRAM our algorithm sorts n integers in the range {0,1, . . . , m-1 } in time O(log n) with $O(n \sqrt{\frac{\log n}{k}})$ operations using ...
Parallel merging with restriction
In this paper, we study the merging of two sorted arrays $A=(a_{1},a_{2},\ldots, a_{n_{1}})$ and $B=(b_{1},b_{2},\ldots,b_{n_{2}})$ on EREW PRAM with two restrictions: (1) The elements of two arrays are taken from the integer range [1, n ], where n = Max ( n 1 , n 2 ). (2) The elements are taken from either ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 2002 Kluwer Academic Publishers.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 01 July 2002
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025
Other Metrics
Citations
Cited By
View all- Bahig HDaoud S(2005)Practical integer sorting on shared memoryProceedings of the First international conference on High Performance Computing and Communications10.1007/11557654_33(271-276)Online publication date: 21-Sep-2005