Parallel Merging and Sorting on Linked List
DOI:
https://doi.org/10.24203/ijcit.v10i2.85Keywords:
Parallel algorithms, optimal algorithms, EREW, CREW, CRCW.Abstract
We study linked list sorting and merging on the PRAM model. In this paper we show that n real numbers can be sorted into a linked list in constant time with n2+e processors or in ) time with n2 processors. We also show that two sorted linked lists of n integers in {0, 1, …, m} can be merged into one sorted linked list in O(log(c)n(loglogm)1/2) time using n/(log(c)n(loglogm)1/2) processors, where c is an arbitrarily large constant.
References
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).
. S. A. Cook. Towards a Complexity Theory of Synchronous Parallel Computation. L’ Enseignement Mathématique, 27, 99-124(1981).
. A. Borodin, J. E. Hopcroft. Routing, merging and sorting on parallel models of computation. Proc. 1982 ACM Sypm. On Theory of Computing (STOC’1982), 338-344(1982)
. S. A. Cook, C. Dwork, R. Reischuk. Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM J. Comput. Vol. 15, No. 1, 87-97(1986).
. 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).
. 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).
. Y. Han, X. Shen. Parallel integer sorting is more efficient than parallel comparison sorting on exclusive write PRAMs. SIAM J. Comput. 31, 6, 1852-1878(2002).
. 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).
. T. Hagerup. Towards optimal parallel bucket sorting. Information and Computation. 75, 39-51(1987).
. C. P. Kruskal. Searching, merging, and sorting in parallel computation. IEEE Trans. Comput., C-32, 942-946(1983).
. L. G. Valiant. Parallelism in comparison provlems. SIAM J. on Computing, Vol. 4. No. 3, 348-355(1975).
. O. Berkman, U. Vishkin. On parallel integer merging. Information and Computation. 106, 266-285(1993).
. N. Goyal. An Arbitrary CRCW PRAM Algorithm for Sorting Integers into the Linked List and Chaining on a Trie. Master’s Thesis. University of Missouri at Kansas City. 2020.
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. Uniform linked lists contraction. In arXiv.org with paper id 2002.05034.
Downloads
Published
Issue
Section
License
Copyright (c) 2021 Yijie Han, Sreevalli Tata
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.
