Parallel Merging and Sorting on Linked List


  • 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



Parallel algorithms, optimal algorithms, EREW, CREW, CRCW.


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.


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 with paper id 2002.05034.



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).