Sorting Real Numbers in Constant Time using n2/logcn Processors

Sorting Real Numbers in Constant Time using n2/logcn Processors

Constant time sorting, sorting real numbers into a linked list, lower bounds for sorting, PRAM (Parallel Random Access Machine), EREW, CREW, CRCW.

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 n2 processors. Previously n numbers can be sorted into a linked list using n2 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 n2/t processors in O(logt) time. Previously n real numbers can be sorted into a linked list using n3 processors in constant time and n2 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 n2/logcn 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.

Yijie Han, Pruthvi Kasani, Sai Swathi Kunapuli

www.ijcit.com

August 2022

peri irawan

pdf

english

text