TY - JOUR
AU - Han, Yijie
AU - Kasani, Pruthvi
AU - Kunapuli, Sai Swathi
PY - 2022/12/01
Y2 - 2023/12/05
TI - Sorting Real Numbers in Constant Time Using n^2/log^cn Processors
JF - International Journal of Computer and Information Technology(2279-0764)
JA - IJCIT
VL - 11
IS - 4
SE - Articles
DO - 10.24203/ijcit.v11i4.278
UR - https://ijcit.com/index.php/ijcit/article/view/278
SP -
AB - <p>We study the sorting of real numbers into a linked list on the PRAM (Parallel Random-Access Machine) model. We show that n real numbers can be sorted into a linked list in constant time using n<sup>2</sup> processors. Previously n numbers can be sorted into a linked list using n<sup>2</sup> processors in O(loglogn) time. We also study the time processor trade-off for sorting real numbers into a linked list on the PRAM (Parallel Random Access Machine) model. We show that n real numbers can be sorted into a linked list with n<sup>2</sup>/t processors in O(logt) time. Previously n real numbers can be sorted into a linked list using n<sup>3</sup> processors in constant time and n<sup>2 </sup>processors in O(loglogn). And then we show that input array of n real numbersĀ can be sorted into linked list in constant time using n<sup>2</sup>/log<sup>c</sup>nĀ processors for any positive constant c. We believe that further reduction on the number of processors for sorting real numbers in constant time will be very difficult if not impossible.</p>
ER -