由於分散式系統具有較佳的容錯能力及擴充性使得此系統越來越受到重視。在分散式
系統中，為了提高系統的使用效率一個檔案時常被分成多個部份分別分佈在多個不同
的節點上。
在這種情形之下，由於在每個節點只有部份的檔案可使用，有時候我們必須藉著多個
甚至所有節點的合作才能解決使用者對此分散檔所發出的質問。如果此分散檔案是任
意分佈的，解決這類質問的資訊傳遞量就需較多，但是如果這個檔案是按照其鍵值的
某一順序排序的，我們就可以用較少的資訊傳遞來解決對此檔案所發出的質問。
在本論文中，我們將討論將一個原先任意分佈之分散檔案根據一個給定的排列在網路
上排序。我們的目標是在不使用過多額外記憶體的限制下，降低由排序過程所產生的
交通荷。我們提出了一個非集中式控制分散式排序演算法。我們的策略是基於分散式
第K 小選擇演算法和分制分割及征服策略。我們的演算法的優點是在排序過程，不使
用過多額外記憶體而且交通負擔是平均分佈在整個網路上。除此之外，我們的演算法
亦具有高度的平行性，此特性亦可降低排序過程所需之時間。對於一個分佈於d 個節
點由N 個記錄構成的大型檔案，在呼叫回應(Shout-edho)網路上，最差的狀況下，我
們的演算法的交通複雜度是O(N+ log( ))。當我們考慮點對點(Point-to-point)
網路，最差的狀況下，在環狀網路(ring)加構下，我們的演算法所需要的交通複雜度
為O( N+ d (logd) long ( )+ )；在高維立方體(hypercube) 架構下，則需要O
(Nlogd+ logdlog( ))。
50006196
50006196