在上篇文章中我們介紹了如何對雙調(diào)序列進行排序，操作過程如下圖所示。

其特征是每次分割都是將原始的序列分成兩個等長序列。

例如：原始序列長度為16，第1次分割將其分為2個長度為8的序列；第2次分割將第1次分割的排序結(jié)果（長度仍為16）分為4個長度為4的序列；第3次分割將第2次分割的排序結(jié)果分為8個長度為2的序列；第4次分割將第3次分割的排序結(jié)果分為16個長度為1的序列。

圖中相鄰的綠色標(biāo)記和藍色標(biāo)記序列構(gòu)成一組進行比較。

為進一步說明，我們定義操作符?，如下圖所示。

兩個操作符?由雙向箭頭連接，表示彼此之間共享數(shù)據(jù)，即下方的?可接收上方的?對應(yīng)操作數(shù)op1，同時上方的?可接收下方的?對應(yīng)操作數(shù)op2。

位于上方的?輸出op1與op2中的較小者，位于下方的?輸出op1與op2的較大者，簡言之?表示對兩個輸入數(shù)據(jù)進行升序排序。

此外，還有一個關(guān)鍵點就是圖中虛線的含義。

可以看到op1與min(op1,op2)在一條直線上，op2與max(op1,op2)在一條直線上。

同一條直線上的兩個數(shù)據(jù)其位置是相同的。

即若op1是0號數(shù)據(jù)，那么min(op1,op2)也必須放到0號位置上，這就是所謂的原位（In-place）運算。

在?操作符的定義下，長度為16的雙調(diào)序列的排序過程如下圖所示。

圖中第1列為二進制數(shù)，表示序列中每個元素在序列中的位置也就是地址，用于體現(xiàn)原位運算的特征。

整個排序過程分為4個階段完成對應(yīng)圖中的Stage 0~Stage3。

在Stage 0中，?的兩個操作數(shù)的地址間距為8（例如，3來自0號地址，95來自8號地址）；在Stage 1中間距為4；在Stage 2中間距為2；在Stage 3中間距為1。

審核編輯：劉清