Sorting Real Numbers in Constant Time Using n^2/log^cn Processors
DOI:
https://doi.org/10.24203/ijcit.v11i4.278Keywords:
Constant time sorting, sorting real numbers into a linked list, lower bounds for sorting, PRAM (Parallel Random Access Machine), EREW, CREW, CRCW,Abstract
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 n2 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/logcn 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.
References
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).
Downloads
Published
Issue
Section
License
Copyright (c) 2022 Yijie Han, Pruthvi Kasani, Sai Swathi Kunapuli
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
The articles published in International Journal of Computer and Information Technology (IJCIT) is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
