PSRS算法

問題的初步處理

PSRS算法（Parallel Sorting by Regular Sampling）：首先設待處理里序列長n，並行機上有p個處理器。為了使問題簡單，我們假設n是p的整倍數。於是將這n個元素劃分為p段，每段中有n/p個元素，將這p段分給p個處理器。注意，執行PSRS算法的並行機必須是多指令流多數據流（MIMD）的。

算法描述

1. 讓各個處理器並行的調用串行排序算法進行局部排序；
2. 從每個有序段中選p個樣本元素，共$p^{2}$個樣本元素（採樣）；、
3. 對樣本元數排序；
4. 從樣本元素中選p-1作為劃分元素，並播送給其餘的處理器；
5. 各個處理器根據劃分元素對局部序列進行劃分（分為p段）；
6. 各個處理器將每一段按段號交換到相應序列號的處理器；
7. 在各個處理器中使用串行算法再次進行局部排序。

算法分析

如果注意到一個好的串行排序算法的時間複雜度為$O(nlogn)$那麼，容易證得上述PSRS算法的時間複雜度在$n>p^{3}$時為$O({\frac {n}{p}}log{n})$。

缺點：我們注意到，在第五步進行主元劃分時時可能會引起不均勻性，即位於某兩個主元之間的元素可能要多一些（多於${\frac {n}{p}}$個）。我們可以證明，在算法中進行到第六步全局交換時，可能會有某一個處理器中數據達到${\frac {2n}{p}}-{\frac {n}{p^{2}}}-(p-1)$個；這樣引起的直接後果是處理器負載不均勻，那麼在歸併排序中可能會引起排序時間的不均勻。

參閱

並行計算 並行排序