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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

審核編輯：劉清