作者 ｜ 張云浩

前言

說到排序算法，很多同學(xué)會想起快速排序、堆排序、冒泡排序這些耳熟能詳?shù)乃惴?。了解得深一些的同學(xué)，也可能看過例如 Python 的 timsort 以及 C++ intro sort 之類的排序算法。

但是我們也會有很多疑問，例如 Go 語言中使用的快速排序和我們書上學(xué)到的快速排序有什么區(qū)別呢?如果我們自己寫一個快排，會比 Go 語言自帶的快嗎?排序算法方面業(yè)界最新的進(jìn)展是什么呢，有沒有一個算法是最快的?

本篇文章會向大家介紹字節(jié)跳動-語言團(tuán)隊在 Go 語言排序算法的實踐，我們使用了 pdqsort 算法 + Go1.18 泛型，實現(xiàn)了一個比標(biāo)準(zhǔn)庫 API 在幾乎所有情況下快 2x ~ 60x 的算法庫。

此項改動已經(jīng)被社區(qū)采納合并進(jìn)入 Go runtime 當(dāng)中，成為默認(rèn)的 unstable 排序算法，預(yù)計將會在 Go 1.19 中和大家見面，其中非泛型版本位于標(biāo)準(zhǔn)庫 sort，泛型版本位于 exp/slices。

Proposal: https://github.com/golang/go/issues/50154

臨時項目地址：https://github.com/zhangyunhao116/pdqsort

簡介

Go、Rust、C ++ 的默認(rèn) unstable 排序算法雖然名義上叫快速排序(quicksort)，但其實質(zhì)是混合排序算法(hybrid sorting algorithm)，它們雖然在大部分情況下會使用快速排序算法，但是也會在不同情況下切換到其他排序算法。

unstable 排序算法意味著在排序過程中，值相等的元素可能會被互相交換位置。

一般來說，常見的混合排序算法，都會在元素較少(這個值一般是 16 ~ 32)的序列中切換成插入排序(insertion sort)，盡管插入排序的時間復(fù)雜度為 O(n^2)，但是其在元素較少時性能基本超越其他排序算法，所以在混合排序算法的方案中被經(jīng)常使用。

在其他情況下，默認(rèn)使用快速排序算法。然而，快速排序算法有可能因為 pivot 選擇的問題(有些序列 pivot 選擇不好，導(dǎo)致性能下降很快)而導(dǎo)致在某些情況下可能到達(dá)最壞的時間復(fù)雜度 O(n^2)，為了保證快速排序算法部分在最壞情況下，我們的時間復(fù)雜度仍然為 O(n* logn)。大部分混合排序算法都會在某種情況下轉(zhuǎn)而使用堆排序，因為堆排序在最壞情況下的時間復(fù)雜度仍然可以保持 O(n* logn)。

一言以蔽之，目前流行的 unstable 排序算法基本都是在不同的情況下，使用不同的方式排序從而達(dá)到最優(yōu)解。而我們今天介紹的 pdqsort 也是這一思想的延伸。

前置知識

介紹一些常見的基本的排序算法以及它們的特性。

Quicksort (classic)

Average-case：O(n*logn) Bad-case：O(n^2)

經(jīng)典的 快速排序(quicksort) 主要采用了分治的思想，具體的過程是將一個 array 通過選定一個 pivot(錨點(diǎn))分成不同的 sub-arrays，選定 pivot 后，使得這個 array 中位于 pivot 左邊的元素都小于 pivot，位于 pivot 右邊的元素都大于 pivot。由此，pivot 兩邊構(gòu)成了兩個 sub-arrays，然后對這些 sub-arrays 進(jìn)行相同的操作(選定 pivot 然后切分)。當(dāng)某個 sub-array 只有一個元素時，其本身有序，此時便可以退出循環(huán)。如此反復(fù)，最后得到整體的有序。

我們可以觀察到，經(jīng)典的 quicksort 主要過程就是兩步：

• choose pivot: 選擇一個 pivot
• partition: 使用 pivot 對 array 進(jìn)行劃分

總的來說，quicksort 的性能關(guān)鍵點(diǎn)在于選定 pivot，選擇 pivot 的好壞直接決定了排序的速度，如果每次 pivot 都被選定為真正的 median(中位數(shù))，此時快排的效率是最高的。因此 pivot 的選擇重點(diǎn)在于尋找 array 真正的 median，目前所有的 pivot 選擇方案都是在尋找一個近似的 median。

為什么 pivot 選定為中位數(shù)使得快排效率最高?

詳細(xì)解釋可以參考：

https://en.wikipedia.org/wiki/Quicksort#Formal_analysis。簡單來說，pivot 如果選定為中位數(shù)，則大部分情況下每次 partition 都會形成兩個長度基本相同的 sub-arrays，我們只需要 logn 次 partition 就可以使得 array 完全有序，此時時間復(fù)雜度為 O(n* logn)。在最壞情況下，我們需要 n-1 次 partition (每次將長度為 L 的 array 分為長度為 1 和 L - 1 的兩個 sub-arrays)才能使得 array 有序，此時時間復(fù)雜度為 O(n^2)。

我們?yōu)楹尾恢苯訉ふ?array 真正的 median?

原因是因為 array 的長度太長的話，尋找真正的 median 是一個非常昂貴的操作(需要存儲所有的 items)，相比于尋找一個近似的 median 作為 pivot 會消耗更多的資源，如果找到正確 median 的消耗比使用一個近似 median 高的話，這就是一個負(fù)優(yōu)化。折中的方案就是使用一個高性能的近似 median 選擇方案。

基本所有針對 quicksort 的改進(jìn)方案，都是通過改造這兩步得到的，例如第一步可以使用多種不同的 pivot 選擇方案(見附錄)，第二步則有諸如 BlockQuickSort 這樣通過減少分支預(yù)測來提升性能的方案。

Insertion sort

插入排序的主要想法是，每一次將一個待排序的元素插入到前方已經(jīng)排序好的序列中，直到插入所有元素。盡管其平均時間復(fù)雜度高達(dá) O(n^2)，但是在 array 長度較短(這個值一般是 16 ~ 32)的情況下，在實際應(yīng)用中擁有良好的性能表現(xiàn)。

Heap sort

堆排序是利用堆結(jié)構(gòu)設(shè)計出來的一種排序算法。這個算法有一個非常重要的特性，其在最壞情況下的時間復(fù)雜度仍然為 O(n* logn)。故而很多混合排序算法利用了這一特性，將堆排序作為 fall back 的排序算法，使得混合排序算法在最壞情況下的理論時間復(fù)雜度仍然為 O(n* logn)。

pdqsort (pattern-defeating quicksort)

論文地址：https://arxiv.org/pdf/2106.05123.pdf

pdqsort (pattern-defating quicksort) 是 Rust、C++ Boost 中默認(rèn)的 unstable 排序算法，其實質(zhì)為一種混合排序算法，會在不同情況下切換到不同的排序機(jī)制，是 C++ 標(biāo)準(zhǔn)庫算法 introsort 的一種改進(jìn)。可以認(rèn)為是 unstable 混合排序算法的較新成果。

其理想情況下的時間復(fù)雜度為 O(n)，最壞情況下的時間復(fù)雜度為 O(n* logn)，不需要額外的空間。

pdqsort 的主要改進(jìn)在于，其對 common cases (常見的情況)做了特殊優(yōu)化。因此在這些情況下性能超越了之前算法，并且相比 introsort 在隨機(jī)序列的排序性能基本保持了一致。例如當(dāng)序列本身有序、完全逆序、基本有序這些情況下都超越了大部分算法。其主要的思想是，不斷判定目前的序列情況，然后使用不同的方式和路徑達(dá)到最優(yōu)解。

這里的算法細(xì)節(jié)描述的是 https://github.com/zhangyunhao116/pdqsort 中的實踐，其大致相當(dāng)于論文中的 PDQ 算法(沒有來自 BlockQuickSort 的優(yōu)化)，并且加入了一些參數(shù)調(diào)整以及借鑒了部分其他 pdqsort 的實踐優(yōu)化。

注意，不同 pdqsort 實踐中會有一些細(xì)微差異(因為語言以及接口的關(guān)系)，不過其總體思想是一致的。

pdqsort C++ 版本性能對比，位于 https://github.com/orlp/pdqsort

整體流程

為了更好地解析 pdqsort 算法，我們先來描述下其主要流程。pdqsort 就是下面三種情況的不斷循環(huán)，根據(jù)序列長度以及是否是最壞情況，每個 array 都會使用下面三種方法之一進(jìn)行排序(有優(yōu)先級，盡可能使用排在前面的方式)

短序列情況，對于長度在 [0, MAX_INSERTION] 的輸入，使用 insertion sort (插入排序)來進(jìn)行排序后直接返回，這里的 MAX_INSERTION 我們在 Go 語言下的性能測試，選定為 24。

最壞情況，如果發(fā)現(xiàn)改進(jìn)的 quicksort 效果不佳(limit == 0)，則后續(xù)排序都使用 heap sort 來保證最壞情況時間復(fù)雜度為 O(n*logn)。

正常情況，對于其他輸入，使用改進(jìn)的 quicksort 來排序，這里的算法分幾步，后續(xù)內(nèi)容會詳細(xì)介紹部分步驟。

圖中淺黃色虛線框代表此步驟為可選項，即算法會根據(jù)情況(以下變量)來決定是否執(zhí)行。

下列變量代表 pdqsort 進(jìn)行本次循環(huán)排序的情況，用于幫助算法來猜測需要排序的 array 的狀態(tài)，來決定某些步驟是否需要進(jìn)行

• wasBalanced: Bool, 代表上次 partition 是否平衡。在 pivot 和真正的 median 很接近時我們認(rèn)為是平衡的(true)，此變量可以用 partition 后的 pivot index 同 array 兩端的距離來判定。
• wasPartitioned: Bool, 如果為真，則代表上次 partition 沒有交換任何元素(即上次 partition 分割的是一個本身已經(jīng)有序的 array)。
• limit: int，如果為 0，則后續(xù)對 unsorted array 的排序都會使用 heap sort 而不是 quick sort。這種情況發(fā)生在 quicksort 有很多次選擇的 pivot 和真正的 median 差距很大，從而導(dǎo)致 partition 后的兩個 sub-arrays 長度相差較大的場景中。limit 的初始值是根據(jù)待排序 array 的長度計算出來的，每次發(fā)現(xiàn)快排策略效果不佳時，即 !wasBalanced 為真，則使得 limit 減小 1。

3-1. 應(yīng)對可能的最壞情況，即實現(xiàn)中的breakPatterns。此時會判斷 wasBalanced 是否為 true，如果不平衡(false)，則隨機(jī)交換幾個元素，破壞一些可能造成 pivot 與 median 相差較大的特殊情況。

3-2. pivot 的選擇，即實現(xiàn)中的 choosePivot。函數(shù)同時返回兩個值，pivotidx 和 likelySorted，前者是 pivot 在此 array 的 index(索引)，后者代表著選擇 pivot 的過程中，是否可以大概率認(rèn)定這個 array 已經(jīng)為有序。

3-3. 應(yīng)對幾乎有序的情況，即實現(xiàn)中的 partialInsertionSort。如果 wasBalanced && wasPartitioned && likelySorted 為 true，則代表此 array 有非常大的可能是一個有序序列。此時我們使用 partial insertion sort 的排序算法，其原理和 insertion sort 大致相當(dāng)，只是多了一個嘗試次數(shù)，即只會對有限的元素進(jìn)行插入排序，增加這個限制是為了避免猜測錯誤導(dǎo)致消耗大量時間。如果達(dá)到嘗試次數(shù)時 array 仍未有序，則退出。如果在嘗試次數(shù)之前發(fā)現(xiàn)所有元素有序，則可以直接返回。

3-4. 應(yīng)對重復(fù)元素較多的情況，即實現(xiàn)中的 partitionEqual 。如果 pred 存在，并且和本次選中的 pivot 值相等(pred 是之前 array 的 pivot，即目前 array 中的最小值，因為與 pivot 重復(fù)的元素只可能出現(xiàn)在 partition 后的兩個 sub-arrays 其中之一)，說明重復(fù)元素很可能較多，則調(diào)用 partitionEqual 然后繼續(xù)進(jìn)行下次循環(huán)，使用這種方法將重復(fù)元素提前放到一起，因為多次選定重復(fù)元素作為 pivot 會使得 partition 的效率較低。

3-5. partition，使用 pivot 來分割 array，即實現(xiàn)中 partition。此函數(shù)和一般快排的 partition 相比基本相同，區(qū)別在于其會檢測序列是否本身就是有序的(即 partition 時沒有交換任何元素)。

實現(xiàn)細(xì)節(jié)

breakPatterns (3-1)

這一步的作用是解決一些會導(dǎo)致現(xiàn)有 pivot 選擇方案表現(xiàn)很差的情況，所以當(dāng)上次 partition 的 pivot 選擇不好時(表現(xiàn)為最終 pivot 的位置離 array 兩端之一很近)，此時會隨機(jī)交換幾個元素來避免一些極端情況。同時，此步驟還會將 limit 減去 1，說明上次 pivot 的選取方案不夠好(當(dāng) limit 為 0 時使用 heapsort 而不是快排方案來進(jìn)行排序)。

pivot 選擇 (3-2)

附錄中有關(guān)于 pivot 選擇方案的詳細(xì)介紹。

假設(shè) array 的長度為 L，SHORTEST_MEDIAN_OF_MEDIANS 值為 50。這里根據(jù)長度分為三種情況：

• L 位于 [0,8): 直接取固定值作為 pivot，即 L/4 * 2
• L 位于 [8,SHORTEST_MEDIAN_OF_MEDIANS): 使用 medians of three 方法采樣 3 個元素篩選 pivot，即 L/4* 1 L/4* 2 L/4* 3 的中間值
• L 位于 [SHORTEST_MEDIAN_OF_MEDIANS, ∞): 使用 Tukey’s median of medians 采樣 9 個元素得到一個近似中間值

此方法還會判斷這個 array 是否很可能已經(jīng)有序，例如當(dāng)?shù)谌N情況時，如果發(fā)現(xiàn) a a-1 a+1 這三個值中，a 恰好是中間值(b,c 也同樣如此)，則說明元素在這些地方都局部有序，所以這個 array 很可能是已經(jīng)有序的。如果每次都發(fā)現(xiàn)，a a-1 a+1 這三個值都是逆序排列(b,c 也同樣如此)，則說明元素在這些地方都局部逆序，整個 array 很可能是完全逆序的。此時的策略是將整個 array 翻轉(zhuǎn)，這樣有很大概率使得整個 array 幾乎有序。

Go 語言環(huán)境下的實踐考量

Go 1.18 泛型對于排序算法的影響

Go 1.18 的泛型在這種情況下有較大的性能提升并且增加了可維護(hù)性，同樣的算法在經(jīng)過泛型改造后能得到 2x 的性能提升。這一點(diǎn)我們通過觀察 pdqsort 泛型版本，以及 pdqsort (with sort.Interface) 的版本性能對比可以觀察出來。

在可維護(hù)性方面，通過泛型的類型約束抽象了所有可比對的基本類型，不需要使用復(fù)雜的代碼生成技術(shù)。

在性能方面，泛型由于有了類型參數(shù)，可以在編譯期生成大量代碼，免去了使用 sort.Interface 帶來的抽象開銷。

pdqsort 相比于 Go 原有算法的優(yōu)勢

在純粹的算法層面，即 pdqsort (with sort.Interface) ，pdqsort 在完全隨機(jī)的情況下和原有算法(類似于 IntroSort)性能幾乎一致(非泛型版本，因為需要兼容 sort.Interface)。在常見的場景下(例如序列有序|幾乎有序|逆序|幾乎逆序|重復(fù)元素較多)等情況下，會比原有的算法快 1 ~ 30 倍。

因此，我們同樣向 Go 官方提議將 pdqsort 應(yīng)用在 sort.Sort 中，相關(guān)的 issue 討論位于：https://github.com/golang/go/issues/50154

Go 原有的算法類似于 introsort，其通過遞歸次數(shù)來決定是否切換到 fall back 算法，而 pdqsort 使用了另一種計算方式(基于序列長度)，使得切換到 fall back 算法的時機(jī)更加合理。

為什么禁用來自 BlockQuickSort 的優(yōu)化

因為 BlockQuickSort 的優(yōu)化基本來自減少分支預(yù)測，原理是在 partition 一個長序列的時候，先存儲需要交換的元素，后續(xù)統(tǒng)一放到真正的序列中。經(jīng)過實際性能測試，發(fā)現(xiàn)這一優(yōu)化在 Go 上并不成立，甚至是一個負(fù)優(yōu)化。原因可能由于 Go 是一門 heap-allocate 的語言，對于此類優(yōu)化并不敏感。并且對于減少分支預(yù)測，Go 的編譯器在某些情況下并不能優(yōu)化到相應(yīng)指令(CMOV)。

總結(jié)

目前大部分工業(yè)界使用的 unstable 排序算法，基本上都從過去教科書中單一的排序算法轉(zhuǎn)變成混合排序算法，來應(yīng)對實踐場景中各式各樣的序列。

pdqsort 依靠其在常見場景相比之前算法的性能優(yōu)勢，逐漸成為 unstable 排序算法的主流實現(xiàn)?；?Go1.18 帶來的泛型，使得排序算法的實現(xiàn)被大大簡化，也給予了我們實現(xiàn)新算法的可能。但是 pdqsort 也不是萬能靈藥，在某些情況下，其他的算法依然保持著優(yōu)勢(例如 Python 標(biāo)準(zhǔn)庫的 timsort 在混合升序&&降序的場景優(yōu)于 pdqsort)。不過在大部分情況下，pdqsort 依靠其對于不同情況的特定優(yōu)化，成為了 unstable 算法較好的選擇。

附錄

quicksort pivot 方案對比

這里簡單介紹不同的 pivot 選擇方案。最好的 pivot 選擇方案就是使用一個高性能的近似 median 選擇方案，在準(zhǔn)確度和性能上達(dá)到平衡。假設(shè)我們需要排序的元素為 [4,3,2,1]，我們需要將其排列為升序，即 [1,2,3,4]。

選擇首個元素

這是我們實現(xiàn)快排時最簡單的方法，即選取 array 的首個元素作為 pivot。

[4,3,2,1]。選定 4 為 pivot，由于左邊沒有元素，所以會從最右邊開始找，找到第一個比 4 小的元素，即 1 作交換。

[1,3,2,4]。選定 1 為 pivot，同理。希望從右邊找到第一個比 1 小的元素，由于 1 已經(jīng)是最小的值，此輪不會交換任何元素。

[1,3,2,4]。選定 3 為 pivot，同理。將 2 和 3 互換。

[1,2,3,4]。得到結(jié)果。

可以看到，選擇首個元素的方式在 array 為逆序的情況下，每輪 partition 只將問題的規(guī)模減小了 1，即每次只能確定一個元素的最終位置。這種簡單的方法在面對極端情況時效果并不好，在完全逆序的情況下達(dá)到了快排的最壞情況。

median of three

這個方法是分別取最左邊、最右邊、中間三個值，然后選出其中間值作為 pivot。例如 [4,3,2,1]，我們會選取 4 3 1 然后選擇其中的 3 作為 pivot。這種方式相比于首個元素的方式會更加合理，因為采樣了多個元素，不容易受到一些極端情況的影響，往往會比首個元素的方式有更好的效果。

stackoverflow discussion:

??https://stackoverflow.com/questions/7559608/median-of-three-values-strategy??

median of medians

這個方法的原理其實和 median of three 相似，不同的地方在于加大了 pivot 的采樣范圍，在 array 長度較長的情況下理論表現(xiàn)會更好。其采樣步驟是先將 array 分為 n/5 個 sub-arrays，n 為 array 的長度。然后將這些 sub-arrays 的 medians 都取出，選取這些 medians 中的 median，同樣的方式如此反復(fù)，最后得到一個 median of medians 作為最后的 pivot。

stackoverflow discussion:

https://stackoverflow.com/questions/5605916/quick-sort-median-selection

Median-finding Algorithm:

??https://brilliant.org/wiki/median-finding-algorithm/#citation-1 ??

John Tukey’s median of medians

此方法其實是 median of three 的改進(jìn)，我們在 median of three 會取三個元素，而 Tukey’s median of medians 會取三個元素及其相鄰兩個元素的 median(例如 median of three 取了 a,b,c 則此方案會選擇 a-1 a a+1 取這三個值的 median)，然后再取這個三個 medians 的 median。即此方案會采樣其中 9 個元素，相比于 median of three 多了三倍的采樣率，所以此方法也叫做 Tukey’s ninther。

See

??https://www.johndcook.com/blog/2009/06/23/tukey-median-ninther/??