作者｜张允浩前言说到排序算法，很多同学都会想到熟悉的算法，比如快速排序、堆排序、冒泡排序。理解更深的同学可能也看过Python的timsort、C++的introsort等排序算法。但是我们也有很多疑问，比如Go语言中使用的快速排序和我们在书上学的快速排序有什么区别？如果我们自己写一个快速排序，会不会比Go语言自带的快？在排序算法方面，业界最新的发展是什么？有没有最快的算法？本文将介绍字节跳动语言团队在Go语言排序算法上的实践。我们使用pdqsort算法+Go1.18泛型，实现了一个几乎在所有情况下都比标准库API快2x~60x的算法库。此更改已被社区采纳并合并到Go运行时中，成为默认的不稳定排序算法。有望在Go1.19与大家见面。非通用版本位于标准库排序中，通用版本位于exp/slices中。提案：https://github.com/golang/go/issues/50154临时项目地址：https://github.com/zhangyunhao116/pdqsort介绍Go、Rust、C++默认的不稳定排序算法在名称排序中称为fast（quicksort），但其实质是一种混合排序算法（hybridsortingalgorithm），虽然他们在大多数情况下会使用快速排序算法，但也会在不同的情况下切换到其他排序算法。一个不稳定的排序算法是指在排序过程中，具有相等值的元素可能会相互交换。一般来说，常见的混合排序算法会在元素较少的序列中切换到插入排序（这个值一般为16~32），虽然插入排序的时间复杂度是O(n^2)，但是其性能基本超越其他排序算法当元素较少时，因此常用于混合排序算法中。在其他情况下，默认使用快速排序算法。但是，快速排序算法由于枢轴选择的问题（某些序列枢轴选择不好，导致性能快速下降），在某些情况下可能会达到最坏的时间复杂度O(n^2)，为了保证在快速排序算法部分的最坏情况，我们的时间复杂度仍然是O(n*logn)。大多数混合排序算法在某些情况下会切换到堆排序，因为堆排序的最坏情况时间复杂度仍然可以保持O(n*logn)。总之，目前流行的不稳定排序算法基本上是在不同的情况下采用不同的排序方式来达到最优解。我们今天介绍的pdqsort也是这种思路的延伸。预备知识介绍一些常用的基本排序算法及其特点。快速排序（经典）Average-case:O(n*logn)Bad-case:O(n^2)经典快速排序（quicksort）主要采用分而治之的思想。具体过程是选择一个数组，通过枢轴（锚点）划分不同的子数组。选择枢轴后，这个数组中枢轴左边的元素比枢轴小，枢轴右边的元素比枢轴大。这样一来，在枢轴的两边形成了两个子数组，然后对这些子数组进行同样的操作（选择枢轴，然后拆分）。当一个子数组只有一个元素时，是有序的，此时可以退出循环。如此反复，最终得到了整体的顺序。我们可以观察到经典快排的主要过程是两步：choosepivot：选择一个pivotpartition：使用pivot划分数组一般来说，quicksort性能的关键在于pivot的选择，它直接决定了pivot的好坏pivot排序的速度，如果每个pivot都选为真正的中位数（median），此时快速排序的效率最高。因此，主元选择的重点是找到数组的真实中位数，而目前所有的主元选择方案都是寻找一个近似的中位数。为什么选择pivot作为中位数，让快速排序效率最高？详细解释请参考：https://en.wikipedia.org/wiki/Quicksort#Formal_analysis。简单的说，如果选择pivot作为中位数，大多数情况下每个partition会形成两个长度基本相同的子数组。我们只需要logn个分区就可以使数组完全有序。此时的复杂度为O(n*logn)。在最坏的情况下，我们需要进行n-1次分区（每次将长度为L的数组分成长度为1和L-1的两个子数组）才能使数组有序，此时的时间复杂度为O(n^2).为什么我们不直接寻找数组的真实中位数呢？原因是如果数组的长度太长，寻找真正的中位数是一个非常昂贵的操作（需要存储所有的项目），相比于寻找一个近似的中位数作为pivot会消耗更多的资源，这是一个负数如果找到正确中位数的成本高于使用近似中位数的成本，则进行优化。折衷方案是使用高性能的近似中值选择方案。基本上所有快速排序的改进方案都是通过对这两个步骤进行改造得到的。例如，第一步可以使用多种不同的枢轴选择方案（见附录），第二步，如BlockQuickSort，可以通过减少分支预测来改进。性能方案。插入排序的主要思想是将一个待排序的元素插入到之前已经排序过的序列中，直到所有的元素都被插入。虽然它的平均时间复杂度高达O(n^2)，但在实际应用中当数组长度较短时（这个值一般为16~32）有很好的表现。堆排序是利用堆结构设计的一种排序算法。该算法有一个非常重要的性质，即其最坏情况下的时间复杂度仍然是O(n*logn)。因此，很多混合排序算法利用了这个特点，将堆排序作为回退排序算法，使得混合排序算法在最坏情况下的理论时间复杂度仍然是O(n*logn)。pdqsort（pattern-defeatingquicksort）论文地址：https://arxiv.org/pdf/2106.05123.pdfpdqsort（pattern-defatingquicksort）是Rust和C++Boost中默认的不稳定排序算法，其本质是一种混合排序算法。它会在不同的情况下切换到不同的排序机制，这是对C++标准库算法introsort的改进。它可以被认为是不稳定混合排序算法的一个相对较新的成果。它的时间复杂度在理想情况下为O(n)，在最坏情况下为O(n*logn)，不需要额外的空间。pdqsort的主要改进是针对commoncase（常见情况）做了专门的优化。因此，在这些情况下，性能超越了之前的算法，introsort在随机序列中的排序性能基本相同。比如当序列本身是有序的，完全颠倒的，基本有序的，就超越了大部分算法。它的主要思想是不断判断当前的序列情况，然后采用不同的方法和路径来达到最优解。这里的算法细节在https://github.com/zhangyunhao116/pdqsort中描述了实践，大致相当于论文中的PDQ算法（没有经过BlockQuickSort的优化），增加了一些参数调整和一些其他的实用优化pdqsort。请注意，不同的pdqsort实现存在一些细微差异（由于语言和接口关系），但总体思路是相同的。pdqsortC++版本性能对比，位于https://github.com/orlp/pdqsort整体流程为了更好的分析pdqsort算法，我们先描述一下它的主要流程。pdqsort是以下三种情况的连续循环。根据序列的长度以及是否为最坏情况，对每个数组使用以下三种方法之一进行排序（优先考虑，尽量使用第一种方法）shortsequence，对于长度为[0,MAX_INSERTION]，使用插入排序（insertionsort）排序，直接返回。在这里，MAX_INSERTION被选择为24，用于我们在Go语言中的性能测试。在最坏的情况下，如果发现改进后的快速排序无效（limit==0），后续排序将使用堆排序来保证最坏情况的时间复杂度为O(n*logn)。一般情况下，对于其他输入，使用改进后的快速排序进行排序。这里的算法分为几个步骤，后面的内容会详细介绍一些步骤。图中淡黄色虚线框表示这一步是可选的，即算法会根据情况（后面的变量）来决定是否执行。以下变量表示pdqsort当前循环排序的状态，用于帮助算法猜测待排序数组的状态，判断是否需要执行某些步骤。wasBalanced：Bool，代表最后一个分区是否平衡。当枢轴非常接近真实中位数时，我们认为它是平衡的（真实的）。这个变量可以通过分区后的主元索引到数组两端的距离来确定。wasPartitioned:Bool，如果为true，则表示上一次分区没有交换任何元素（即上一次分区拆分的是一个已经有序的数组）。limit:int，如果为0，后续对未排序数组的排序将使用堆排序，而不是快速排序。当quicksort多次选择的pivot和真正的中位数差距很大时，就会出现这种情况，导致划分后的两个子数组的长度相差很大。limit的初始值是根据待排序数组的长度来计算的。每次发现快排策略失效，即!wasBalanced为真，则限制减少1。3-1。为了应对最坏的情况，即在实现中使用breakPatterns。这个时候会判断wasBalanced是否为true。如果不平衡（false），则随机交换几个元素来破坏一些可能导致pivot和median差异较大的特殊情况。3-2.pivot的选择，即实现中的choosePivot。函数同时返回两个值，pivotidx和likelySorted，前者是pivot在这个数组中的索引（index），后者表示数组在排序过程中是否能被确定为大概率排序选择枢轴的过程。3-3。处理几乎有序的情况，实现中的partialInsertionSort。如果wasBalanced&&wasPartitioned&&likelySorted为真，则说明该数组很可能是有序序列。这时候我们就使用偏插入排序的排序算法。它的原理和插入排序大致相同，只是多了一次尝试次数，即只会对有限数量的元素进行插入排序。加入这个限制是为了避免猜测错误而消耗大量时间。如果尝试次数达到时数组仍未排序，则退出。如果在尝试次数之前发现所有元素都有序，则可以直接返回。3-4。处理重复元素较多的情况，即实现中的partitionEqual。若pred存在且等于本次选择的主元值（pred为上一个数组的主元，即当前数组中的最小值，因为与pivot重复的元素只能出现在两个子数组中的一个中partition之后），说明可能有很多重复的元素，然后调用partitionEqual继续下一次循环，用这个方法把重复的元素提前放在一起，因为多次选择重复的元素作为pivot会使得效率分区较低。3-5。partition，使用pivot对数组进行拆分，实现上就是partition。这个函数与一般快速排序的划分基本相同，不同的是它会检测序列本身是否有序（即划分时没有元素交换）。实现细节breakPatterns(3-1)步骤的作用是解决一些会导致现有的pivotselectionscheme表现不佳的情况，所以当最后一个partition的pivotselection不好时（表示为final的positionpivot离数组两端很远，其中一个很近），这时候会随机交换几个元素，避免一些cornercase。同时这一步也会将limit减1，说明最后一个pivot的选择方案不够好（当limit为0时，使用heapsort代替quicksort方案进行排序）。枢轴选择（3-2）附录对枢轴选择方案有详细介绍。假设数组的长度为L，SHORTEST_MEDIAN_OF_MEDIANS值为50，这里根据长度分为三种情况：L位于[0,8]：直接取一个固定值作为主元，即L/4*2Lislocatedat[8,SHORTEST_MEDIAN_OF_MEDIANS]:用三法取中值对3个元素进行pivot过滤，即L/4*1L/4*2L/4*3的中值L位于[SHORTEST_MEDIAN_OF_MEDIANS,∞):使用Tukey中位数的中位数对9个元素进行采样得到一个近似的中值。这个方法也是判断这个数组有没有可能已经有序了，比如第三种情况，如果发现aa-1a+1的三个值中，a刚好是中间值(b,c也一样），说明元素在这些地方是局部有序的，所以这个数组很可能已经有序了。如果每次都发现aa-1a+1的三个值的顺序是倒序的（b和c也一样），说明这些地方的元素部分颠倒了，而整个阵法很可能被彻底逆转。这时候的策略是把整个阵法翻转过来，这样大概率整个阵法差不多就齐了。Go语言环境中的实际考虑Go1.18泛型对排序算法的影响在这种情况下，Go1.18的泛型在性能上有了很大的提升，增加了可维护性。同样的算法经过泛型变换后可以获得2x的性能提升。我们可以通过观察pdqsort的通用版本和pdqsort版本（带有sort.Interface）的性能比较来观察这一点。在可维护性方面，所有可比较的基本类型都是通过泛型类型约束抽象出来的，没有使用复杂的代码生成技术。在性能方面，因为泛型有类型参数，所以可以在编译时生成大量代码，消除了使用sort.Interface带来的抽象开销。pdqsort相对于Go原有的算法，优势在于纯算法层面，即pdqsort（有sort.Interface）。在完全随机的情况下，pdqsort的性能几乎和原来的算法一样（类似于IntroSort）（非泛型版本，因为需要兼容sort.Interface）。在常见的场景下（比如序列顺序|几乎顺序|倒序|几乎倒序|重复元素多），会比原算法快1到30倍。因此，我们也向Go官方提议在sort.Sort中应用pdqsort。相关issue讨论位于：https://github.com/golang/go/issues/50154Go的原始算法类似于introsort，通过递归次数来决定是否切换到fallback算法，而pdqsort使用另一种计算方式（基于序列长度），使得切换到fallback算法的时机更加合理。为什么禁用BlockQuickSort的优化，因为BlockQuickSort的优化基本上来自于减少分支预测。原理是在划分一个长序列时，先把需要交换的元素存起来，然后统一放到真正的序列中。经过实际性能测试，发现这个优化在Go上并不成立，甚至是负优化。原因可能是Go是一种堆分配语言，对此类优化不敏感。并且为了减少分支预测，Go的编译器在某些情况下无法优化到相应的指令（CMOV）。综上所述，目前业界使用的大部分不稳定排序算法，基本上已经从教科书上的单一排序算法，变成了实际场景中处理各种序列的混合排序算法。pdqsort凭借其在常见场景下相较于以往算法的性能优势，逐渐成为不稳定排序算法的主流实现方式。基于Go1.18带来的泛型，大大简化了排序算法的实现，也给了我们实现新算法的可能。但是pdqsort并不是万能的。在某些情况下，其他算法仍然保持优势（例如Python标准库的timsort在混合升&&降序场景下优于pdqsort）。然而，在大多数情况下，pdqsort是不稳定算法的更好选择，这取决于它针对不同情况的特定优化。附录快速排序主元方案的比较这里简单介绍一下不同的主元选择方案。最好的枢轴选择方案是使用高性能的近似中值选择方案，以达到准确性和性能之间的平衡。假设我们需要排序的元素是[4,3,2,1]，我们需要将它们按升序排列，即[1,2,3,4]。选择第一个元素这是我们实现快速排序最简单的方法，即选择数组的第一个元素作为基准。[4,3,2,1]。选择4作为基准，因为左边没有元素，所以会从最右边开始查找，找到第一个小于4的元素，即1进行交换。[1,3,2,4]。选择1作为主元，同理。希望找到从右边开始第一个小于1的元素，因为1已经是最小值，所以这一轮不会交换任何元素。[1,3,2,4]。选择3作为主元，同理。交汇处2和3。[1,2,3,4]。得到了答案。可以看出，当按照数组的逆序选择第一个元素时，每轮partition只将问题的大小减1，即每次只能确定一个元素的最终位置。这种简单的方法在面对极端情况时效果不佳，在完全逆序的情况下达到快速排序的最坏情况。三中法就是分别取最左、最右、中间三个值，然后取中间的值作为轴心。例如[4,3,2,1]，我们将选择431然后选择3作为基准。这种方法比第一个元素的方法更合理，因为采样了多个元素，不容易受到一些极端情况的影响，往往比第一个元素的方法有更好的效果。stackoverflow讨论：https://stackoverflow.com/questions/7559608/median-of-three-values-strategymediansofmedians方法的原理其实和medianofthree差不多，不同的是增加了pivot的采样范围，阵列长度越长理论性能越好。采样步骤是先将数组分成n/5个子数组，其中n为数组的长度。然后取出这些子数组的中位数，选择这些中位数的中位数，以同样的方式重复，最后得到中位数的中位数作为最终的主元。stackoverflow讨论：https://stackoverflow.com/questions/5605916/quick-sort-median-selectionMedian-finding算法：https://brilliant.org/wiki/median-finding-algorithm/#citation-1JohnTukey的medianofmedians这种方法其实是对medianofthree的改进，我们会在medianofthree中取三个元素，而Tukey'smedianofmedians会取三个元素和两个相邻元素的中位数（比如medianofthreea,b,c被选中，本方案会选择a-1aa+1取这三个值的中位数），然后取这三个中位数的中位数。也就是说，这个方案会采样9个元素，相对于三个中位数是采样率的三倍，所以这个方法也被称为Tukey'sninth。参见https://www.johndcook.com/blog/2009/06/23/tukey-median-ninther/
