Parallel Merging and Sorting on Linked List

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.