Optimal Sorting Algorithms on Bus-Connected Processor Arrays

概要

論文の詳細を見る
This paper presents a parallel sorting algorithm which sorts n elements in O(n / w+n log n / p) time using p(≦n) processors arranged in a 1-dimensional grid with w (≦n^<1-ε>) buses for every fixed ε>0. Furthermore, it is shown that n×p elements can be sorted in O(n / w+n log n / p) time on p×p (p≦n) processors arranged in a 2-dimensional grid with w(≦n^<1-ε>) buses in each column and in each row. These algorithms are optimal because their time complexities are equal to the lower bounds.
社団法人電子情報通信学会の論文
1993-11-25