Parallel Merging and Sorting on Linked List

Authors

  • Yijie Han School of Computing and Engineering, University of Missouri at Kansas City, USA
  • Sreevalli Tata School of Computing and Engineering, University of Missouri at Kansas City, USA

DOI:

https://doi.org/10.24203/ijcit.v10i2.85

Keywords:

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.

Published

2021-03-30

How to Cite

Han, Y., & Tata, S. . (2021). Parallel Merging and Sorting on Linked List. International Journal of Computer and Information Technology(2279-0764), 10(2). https://doi.org/10.24203/ijcit.v10i2.85

Issue

Section

Articles