平行排序方法

Abstract

在這篇博士論文中，首先我們將回顧過去的學者專家對於平行排列方法(Parallel Sorting Algorithms) 所做的研究與貢獻，我們同時亦將指出在平行排序方法中有一 個非常重要的方法，那就是貝契爾奇偶式的合併排序方法(Batcher's Odd-Even Merge Algorithm)，許許多多平行排序和合併的方法都是基於這個方法所發展出來的 因為貝契爾奇偶式的合併排序方法是二元排序器(２－sorter)為基本運算單元，進而 我們提出以三元排序器(３－sorter)為基本運算單元的平行排序方法，並且本文中亦 將採討、證明利用三元排序器的許多特性。我們將更進一步地提出一個平行排序方法 ，它的基本運算單元則是k 元排序器(k-sorter)k 可為任意的一個正整數，我們然後 證明利用此法能在０(k n )步驟內將k 個數排序完畢，同時我也將證明貝契爾奇偶式 的合併排序方法乃是方法的一個特例。最後我們將導出利用k 元排序器去做平行合併 的最少需要量，然後藉此證明我們提出的k 元排序器的平行合併方法所用的k 元排序 器最少需要量的k ＋ 倍。