Batcher歸併網絡
Batcher排序網絡（英語：Batcher odd–even mergesort）是由一系列Batcher比較器（Batcher's Comparator）組成的。Batcher比較器是指在兩個輸入端給定輸入x,y，再在兩個輸出端輸出最大值max{x,y}和最小值min{x,y}。
比較器網絡是用Batcher比較器連成的完成某一功能的網絡。
所謂雙調序列（Bitonic Sequence）是指由一個非嚴格增序列X和非嚴格減序列Y（其中X的最小元素正好是Y的最大元素）構成的序列，比如序列（23,10,8,3,5,7,11,78）。
定義：一個序列a1,a2,…,an是雙調序列，如果：
- 存在一個ak(1≤k≤n),使得a1≥…≥ak≤…≤an成立；或者
- 序列能夠循環移位滿足條件（1）
奇偶歸併網絡
輸入兩個已排好序的序列，對這兩個序列進行歸併排序，在串行算法中的時間複雜度為O(n)。在並行計算中可以用奇偶歸併算法來實現的。以輸入的兩個4元素有序序列為A和B為例，首先將這兩個序列進行逆洗牌（Unshuffle）得到兩個序列：其中一個是由A,B中奇數號元素組成的序列，記作奇序列OM，另一個則是由A,B中偶數號元素組成的序列，記作偶序列序列EM。接着將OM送入（2,2）奇歸併器中，將EM送入（2,2）偶歸併器中。於是得到一組有序的奇序列和一組有序偶序列。最後除了奇序列一個元素之外將這兩個序列進行洗牌（Shuffle）比較操作即可得到一個有序序列。
算法的遞歸性：一個n階的歸併器是由兩個n/2階的歸併器加一個洗牌比較網絡構成的。比如上面的兩個（2,2）歸併器和最後的洗牌比較網絡就構成了一個（4,4）的歸併器。
一個四階奇偶歸併的例子：假設歸併前的的序列是（1,5,7,6）和（2,3,4,9），那麼第一次操作就將（1,2,7,4）送入（2,2）歸併器中歸併，得到結果為（1,2,4,7）；（5,3,6,9）送入（2,2）歸併器中歸併，得到結果為（3,5,6,9），接着將這兩個排號序的序列進行洗牌比較：(1,3<->2,5<->4,6<->7,9)=>(1,2,3,4,5,6,7,9)。
可以證明這個算法是正確的，我們要用到高德納（Donald Ervin Knuth）的0-1原理，我們發現，對於輸入的任意兩個有序的0,1序列，奇序列與偶序列正好相差0個，1個或2個0。由於奇序列的第一個元素不參與最後的洗牌比較，所以參與比較的0,1數偶只有0個或1個，所以對0,1序列一定能夠得到正確的排序。故而對任意的序列，奇偶歸併網絡可以產生正確的排序。
雙調歸併網絡
雙調歸併網絡是基於Batcher定理而構建的。Batcher定理是說將任意一個長為2n的雙調序列A分為等長的兩半X和Y，將X中的元素與Y中的元素一一按原序比較，即 與 比較，將較大者放入MAX序列，較小者放入MIN序列。則得到的MAX和MIN序列仍然是雙調序列，並且MAX序列中的任意一個元素不小於MIN序列中的任意一個元素。
根據這個原理，我們可以將一個輸入的n元素雙調序列首先通過洗牌比較操作得到一個MAX序列和一個MIN序列，然後通過兩個n/2階雙調歸併器處理就可以得到一個有序序列。
這個算法也是遞歸的，因為n階的雙調歸併器是由一個洗牌比較網絡兩個n/2階的雙調歸併器組成的。