返回Google圖書搜尋

Time-space Optimal Parallel Merging and Sorting

出版	University of Tennessee, Computer Science Department, 1989
URL	http://books.google.com.hk/books?id=75q8HAAACAAJ&hl=&source=gbs_api

註釋Abstract: "A parallel algorithm is time-space optimal if it achieves optimal speedup and if it uses only a constant amount of extra space per processor even when the number of processors is fixed. Previously published parallel merging and sorting algorithms fail to meet at least one of these criteria. In this paper, we present a parallel merging algorithm that, on an EREW PRAM with k processors, merges two sorted lists of total length n in O(n/k + log n). We also describe a stable version of our parallel merging algorithm that is similarly time- space optimal on an EREW PRAM. These two parallel merges naturally lead to time-space optimal parallel sorting algorithms."