EFFICIENT AND SCALABLE QUICKSORT ON A LINEAR-ARRAY WITH A RECONFIGURABLE PIPELINED BUS SYSTEM

Based on the current fiber optic technology, a new computational model , called a linear array with a reconfigurable pipelined bus system (LA RPBS), is proposed in this paper. A parallel quicksort algorithm is im plemented on the model, and its time complexity is analyzed. For a set of N numbers, the quicksort algorithm reported in this paper runs in O(log(2) N) average time on a linear array with a reconfigurable pipel ined bus system of size N. if the number of processors available is re duced to P, where P < N, the algorithm runs in O((N/P) log(2) N) avera ge time and is still scalable. Besides proposing a new algorithm on th e model, some basic data movement operations involved in the algorithm are discussed. We believe that these operations can be used to design other parallel algorithms on the same model. Future research in this area is also identified in this paper. (C) 1998 Elsevier Science B.V.