Sorting Real Numbers into a Linked List on the PRAM Model

Abstract

We study the sorting of real numbers into a linked list on the PRAM (Parallel Random Access Machine) model. The research work consists of two parts. First part talks about the various techniques involved in sorting the real numbers on the linked list in terms of number of processors and time complexity. We have examined on how to sort the real numbers in the linked list using n^3, n^2 processors which has the time complexity of constant time and O(loglogn) time respectively. We have done good research in that area to come up with an algorithm to sort n real numbers into the linked list using n^2 processors in constant time. In second part, we talk about the time processor trade off for sorting the real numbers in the linked list.