Batcher Merge如何在高層次上工作？

Question

我試圖理解Batcher Sort的概念。然而，我在網上找到的大多數資源都完全集中在證明或低級僞代碼上。在查看證據之前，我想了解Batcher Sort的工作原理。有人可以給出關於Batcher Sort如何工作（特別是合併）的高層次概述，而不需要過度冗長的僞代碼（我想知道Batcher Sort背後的想法，而不是實現它）？謝謝！

Answer 1

計時器的排序是與Batcher的合併合併。

要合併兩個數組A和B，Batcher的合併將A以正向順序與B按相反順序連接，從而創建一個雙音素數組。然後它應用了Batcher的雙向排序。

巴特爾的雙聲道排序是快速排序的表親。它將數組分成兩部分，進行一些交換以確保前半部分中的元素不會比第二部分中的元素大，然後遞歸地對半部分進行排序。

如果數組可以旋轉以使其元素增加然後減小，則該數組是可調的。通過不知情的排序的零一原則，足以證明零一輸入的正確性，現在我們做出這個假設。的可能性是

0^a 1^b 0^c = 0 ... a copies ... 0 1 ... b copies ... 1 0 ... c copies ... 0 (rotate right by c positions) 

和

1^a 0^b 1^c (rotate left by a positions) 

其中a，b，c是非負整數。所述雙調排序第一分割此陣列中的兩個大小相等的半部A和B有幾個可能性：

A = 0^w 
B = 1^x 0^y 1^z 

或

A = 0^w 1^x 
B = 1^y 0^z 

或

A = 0^w 1^x 0^y 
B = 1^z 

或其它三個零和一個互換。 Batcher的見解是，通過對A [i]，B [i]應用一個比較器，A是全零，B是雙音的，或者A是雙音的，而B是全1。無論如何，滿足遞歸排序的前提條件。

唯一的非平凡的情況是

A = 0^w 1^x 
B = 1^y 0^z 

及其補充。如果w> = y，則A，B變成

A = 0^(w+x) 
B = 1^y 0^(w-y) 1^x 

所以A是全零和B是雙音的。如果w < y，則

A = 0^w 1^(y-w) 0^z 
B = 1^(y+z) 

因此B是全部1，並且A是雙音速的。如果我們對A和B進行遞歸排序，那麼它們的連接就是已排序的數組。