Open Access
Subscription Access
Sorting Real Numbers in Constant Time using n2 /logc n Processors
We study the sorting of real numbers into a linked list on the PRAM (Parallel Random-Access Machine) model. We show that n real numbers can be sorted into a linked list in constant time using n2 processors. Previously n numbers can be sorted into a linked list using n 2 processors in O(loglogn) time. We also study the time processor trade-off for sorting real numbers into a linked list on the PRAM (Parallel Random Access Machine) model. We show that n real numbers can be sorted into a linked list with n2 /t processors in O(logt) time. Previously n real numbers can be sorted into a linked list using n3 processors in constant time and n2 processors in O(loglogn). And then we show that input array of n real numbers can be sorted into linked list in constant time using n2 /logc n processors for any positive constant c. We believe that further reduction on the number of processors for sorting real numbers in constant time will be very difficult if not impossible.
Keywords
Constant time sorting, sorting real numbers into a linked list, lower bounds for sorting, PRAM (Parallel Random Access Machine), EREW, CREW, CRCW.
User
Font Size
Information
- R. Anderson, G. Miller. Deterministic parallel list ranking. Algorithmic, Vol. 6, 859-868(1991).
- P. Beame, J. Hastad. Optimal bounds for decision problems on the CRCW PRAM. Proc. 1987 ACM Symp. On Theory of Computing (STOC’1987), 83-93(1987).
- P.C.P. Bhatt, K. Diks, T. Hagerup, V.C. Prasad, T. Radzik, S. Saxena. Improved deterministic parallel integer sorting. Information and Computation, 94, 29-47(1991).
- S. A. Cook. Towards a Complexity Theory of Synchronous Parallel Computation. L’ Enseignement Mathématique, 27, 99-124(1981).
- T. Goldberg, U. Zwick. Optimal deterministic approximate parallel prefix sums and their applications. Proc. 3rd. Israel Symp. On Theory and Computing Systems, 220-228(1995).
- T. Hagerup. Towards optimal parallel bucket sorting. Information and Computation. 75, 39-51(1987).
- Y. Han, N. Goyal, H. Koganti. Sort Integers into a Linked List. Computer and Information Science. Vol. 13, No.1, 51-57(2020).
- Y. Han, P. Kasani. Sorting real numbers into a linked list on the PRAM model. {it Proceedings of the 2021 Int. Conf. on Life Sciences, Engineering and Technology}. 45-49(2021).
- Y. Han, P. Kasani. Time processor trade-off for sorting real numbers into a linked list. Proc. International Conference on Computation Structures and Algorithms. 40-44(2021).
- Y. Han, T. Sreevalli. Parallel merging and sorting on linked list. International Journal of Computer and Information Technology (IJCIT). Vol. 10, No. 2, (March 2021), to appear.
- Y. Han. Uniform linked list contraction. Paper 2002.05034 in arXiv.org.
- Y. Han. Matching partition a linked list and its optimization. Proc. 1989 ACM Symposium on Parallel Algorithms and Architectures (SPAA'89), 246-253 (June 1989).
- Y. Han. Parallel algorithms for computing linked list prefix. Journal of Parallel and Distributed Computing 6, 537-557(1989).
- J.J´aJ´a. An Introduction to Parallel Algorithms. Addison Wesley, Reading, MA, 1992.
- R. M. Karp, V. Ramachandran, Parallel algorithms for shared-memory machines. In Handbook of Theoretical Computer Science (Vol. A): Algorithms and Complexity, J. van Leeuwen, Ed., New York, NY: Elsevier, 869-941(1991).
- C. P. Kruskal. Searching, merging, and sorting in parallel computation. IEEE Trans. Comput., C-32, 942-946(1983).
- L. G. Valiant. Parallelism in comparison problems. SIAM J. on Computing, Vol. 4. No. 3, 348-355(1975).
Abstract Views: 122
PDF Views: 88