Batcher合併網路

Batcher 排序網路是由一系列Batcher 較器（Batcher's Comparator）組成的。Batcher 較器是講佇兩个輸入端予定輸入 x , y，閣佇兩个輸出端輸出上大值 max { x , y } 佮上小值 min { x , y }。

較器網路的是用 Batcher 較器連成的完成某一功能的網路。

所謂雙調序列（Bitonic Sequence）是講由一个非嚴格增加序列 X 佮非嚴格減序列 Y（其中 X 的上小元素拄仔好是 Y 的上大元素）構成的序列，比如序列（二十三 , 十 , 八 , 三 , 五 , 七 , 十一 , 七十八）。

定義：一个序列 a 一 , a 二 ,…, an 是雙調序列（Bitonic Sequence），若是：

一 . 存在一个 ak ( 一 ≤k≤n ) , 予得 a 一 ≥…≥ak≤…≤an 成立；抑是二 . 序列會當轉去箍徙位滿足的條件（一）

尪仔合併網路

輸入兩个已經照排好勢的序列，嘿這兩个序列進行合併排序，佇咧串行演算法內面的時間複雜度做 O ( n )。佇平行計算中會當用奇尪仔合併演算法來實現的。以輸入的兩个四元素順序列做 A 和 B 做例，首先將這兩个序列來進行逆洗牌（Unshuffle）得著兩个序列：其中一个是由著 A , B 中奇數號元素組成的序列，記作奇序列 OM，另外一个只是由著 A , B 中偶數號元素組成的序列，記作偶序列序列 EM。紲落來共 OM 送入（二 , 二）是奇合併器內底，將 EM 送入（二 , 二）尪仔合併器當中。所以得著一組有序的奇序列和一組有序尪仔序列。最後除了奇序列一个元素以外將這兩个序列來進行洗牌仔（Shuffle）比較操作即可得著一个順序列。

演算法的遞迴性：一个 n 階的合併器是由兩个 n / 二階的合併器加一个洗牌較網路構成的。譬如講頂懸的兩个（二 , 二）會合併器佮最後的洗牌較網路就構成一个（四 , 四）的合併器。

一个四階奇偶合併的例：假使佮併前的序列是（一 , 五 , 七 , 六）和（二 , 三 , 四 , 九）， 遐頭一擺操作就將（一 , 二 , 七 , 四）送入（二 , 二）合併器當中合併，得著結果為（一 , 二 , 四 , 七）；（五 , 三 , 六 , 九）送入（二 , 二）合併器當中合併，得著結果為（三 , 五 , 六 , 九）， 紲落來將這兩个排號序的序列進行洗牌較：( 一 , 三 <-> 二 , 五 <-> 四 , 六 <-> 七 , 九 )=> ( 一 , 二 , 三 , 四 , 五 , 六 , 七 , 九 )。

證明這个演算法是正確的，咱欲用去高德納（Donald Ervin Knuth）的零吱一原理，阮有發現講，對輸入的任意兩个有序的零 , 一序列，奇序列佮尪仔序列拄好精差零个，一个抑是兩个空。因為奇序列的頭一个元素無參與最後的洗牌較，所以參與較的零 , 一數偶干焦零个抑是一个，所以對零 , 一序列一定會當得著正確的排序。故工對任意的序列，尪仔合併網路會當產生正確的排序。

雙調合併網路

雙調合併網路是基於Batcher 定理而構建的。Batcher 定理是講共任意一个長為二 n 的雙調序列 A 成做等長的兩半 X 和 Y，將 X 中的元素佮 Y 中元素一一揤原序較，即 $ a _ { i } $ 佮 $ a _ { i + n } ( i \ leq n ) $ 比較，共大家囥入去 MAX 序列，較細个人放入 MIN 序列。則得著的 MAX 和 MIN 序列原仔是雙調序列，並且 MAX 序列內底的任意一个元素無小於 MIN 序列內底的任意一个元素。

根據這个原理，咱會當將一个輸入的 n 元素雙調序列首先通過洗牌仔較操作得著一个 MAX 序列佮一个 MIN 序列，然後通過兩个 n / 二階雙調合併器處理就會當得著一个順序列。

這个演算法嘛是遞迴的，因為乎 n 階的雙調合併器是由一个洗牌較網路兩个 n / 二階的雙調合併器組成的。

參閱

• 平行計算
• 洗牌交換連接