Sorting Real Numbers in Constant Time Using n^2/log^cn Processors

Authors

  • Yijie Han School of Computing and Engineering, University of Missouri, Kansas City, USA
  • Pruthvi Kasani School of Computing and Engineering, University of Missouri, Kansas City, USA
  • Sai Swathi Kunapuli School of Computing and Engineering, University of Missouri, Kansas City, USA

DOI:

https://doi.org/10.24203/ijcit.v11i4.278

Keywords:

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.

Author Biographies

Pruthvi Kasani, School of Computing and Engineering, University of Missouri, Kansas City, USA

Pruthvi Kasani was born in Vijayawada, Andhra Pradesh, India on August 6th 1997. He
attended elementary school named as Nirmala High School and graduated as the top scorer of
that academic year 2013. Later, he got admitted into one of the top colleges in the nation and
finished his bachelor’s from “Indian Institute of Information Technology, Chennai”. In the
year 2015, he was placed in a MNC called ADP and worked for a year and half. During Jan
2021, he entered University of Missouri Kansas City to complete his Master of Science Degree
in Computer Science in May 2022. He was awarded the outstanding master's student at School of Computing and Engineering, University of Missouri at Kansas City.

Sai Swathi Kunapuli, School of Computing and Engineering, University of Missouri, Kansas City, USA

Sai Swathi Kunapuli is currently a master's student at University of Missouri at Kansas City. She is taking classes and working toward her master's degree.

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

2022-12-01

How to Cite

Han, Y., Kasani, P., & Kunapuli, S. S. . (2022). Sorting Real Numbers in Constant Time Using n^2/log^cn Processors. International Journal of Computer and Information Technology(2279-0764), 11(4). https://doi.org/10.24203/ijcit.v11i4.278

Issue

Vol. 11 No. 4 (2022): August 2022

Section

Articles

License

Copyright (c) 2022 Yijie Han, Pruthvi Kasani, Sai Swathi Kunapuli

Creative Commons License

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.