排序算法
世界上有很多种对序列排序的算法（序列可以不是整数序列，只要可比较即可）。
\(O(n^2)\) 算法
这类算法需要 \(O(n^2)\) 次比较+访问。
选择排序（selection sort）
每次选择最小元素，并且和最小元素所在位置交换。
插入排序（insertion sort）
遇到新元素就将元素插入到正确的位置。
地精排序（gnome sort）
和插入排序差不多，但是比插入排序慢。
冒泡排序（bubble sort）
从结尾开始，每次从头到尾扫一遍，看到逆序对就交换。
鸡尾酒排序（cocktail sort）
双向冒泡排序。
梳子排序（comb sort）
对一个间隔上的数列进行排序，排完把间隔大小除以 \(1.3\)。一直排序直到排好序。
\(O(n\log n)\) 算法
希尔排序（shell sort）
是历史上第一个突破 \(O(n^2)\) 的排序算法。
和梳子排序差不多，但是间隔大小被除以 \(3\)。
快速排序（quick sort）
取一个序列中的值（成为枢轴（pivot）），把序列分成小于它、等于它、大于它三部分，对两边进行递归。
归并排序（merge sort）
把一个序列对半分，排序完两半将结果归并。
堆排序（heap sort）
选择排序的变种。使用“堆”这种数据结构实现 \(O(\log n)\) 找到最大/最小值。
还可以更快吗？
最坏情况
不可以。这是信息论的结果：对任意 \(n\) 个数排序最少需要 \(O(n\log n)\) 次操作。
最好情况
但是对于部分数列，某些算法可以实现 \(O(n)\)，如插入排序应对已经排好序的数列就是 \(O(n)\) 的。为了应对这样的情况，我们设计了如下这些算法。
混合型算法
Introsort
这是 std::sort 的实现。它通过给快速排序的框架加上一个递归深度限制（超过则切换为堆排序），并在输入过小时切换为插入排序得到。
时间复杂度：最好 \(O(n\log n)\)，平均 \(O(n\log n)\)，最坏 \(O(n\log n)\)。
PDQ-sort
在 Introsort 上修改。
- 如果分割这一步交换元素的次数小于某个阈值，就对整个序列进行一次插入排序，如果交换次数过多就继续递归，否则直接返回。
- 如果分割得到的数列太不平衡，则递归深度 \(+1\)，并打乱下轮可能被选为枢轴的元素，否则递归深度不变。递归深度额度减小。
Timsort
在归并排序上修改。Python list.sort 使用了该算法。
引入一个栈，初始为空。
- 把递归过程换成边扫数组边归并。如果扫到了一个长度大于某个阈值的递增/递减序列（如果递减就把它反转），就把它的索引存下来。如果扫到的递增/递减序列太短就用插入排序把它变成前一种情况。
- 存下来索引之后对栈顶的元素进行永久循环，直到以下两个条件都被满足：（假设栈顶区间为 \(X\)，第二个是 \(Y\)，第三个是 \(Z\)）
\(|Y|>|X|\)
\(|Z|>|Y|+|X|\)
- 扫完数组之后把栈里的所有区间归并得到结果。
性能比较
下表列出了许多主流排序算法的性能。表头是算法名字，在上面都有提到。
第一列（数据大小、类别）
random：随机数据。
ascending：单调递增数据。
descednding：单调递减数据。
pipe organ：前半升后半降。
final merge：前半 \([\frac n2,n)\)，后半 \([0,\frac n2)\)。
final merge reversed：前半从 \(n-1\) 降到 \(1\)（只有奇数），后半从 \(n-2\) 降到 \(0\)（只有偶数）。
heapified：从排好序的数组建大根二叉堆。
binary search tree：\([\frac n{2^k},\frac n{2^{k-1}})\) 是所有二进制非零位是第 \(k-1\) 位的数按大小排好序。
sawtooth：四个单调降的序列。
scrambled head, scrambled tail：头/尾 \(\frac18\) 是打乱后的所有 \(8\) 的倍数，其余仍然保持，每 \(8\) 个元素缺一个 \(8\) 的倍数。
half-reversed：排好序的序列前 \(\frac14\) 和后 \(\frac14\) 从外到内交换。不是直接交换区间！
adversary：见这篇文章。
表格 Part.1
这部分是对于所有算法在 \(n=2^{10},2^{14},2^{17}\) 时的性能。
| data size | std::sort | std::stable_sort | Timsort | PDQ-sort | Insertion sort | Selection sort | Bubble sort | Cocktail sort | Gnome sort | Comb sort | Merge sort | Heap sort | Smooth sort | Shell sort | Bitonic sort | Quick sort (LR, pivot=first) | Quick sort (LR, pivot=last) | Quick sort (LR, pivot=middle) | Quick sort (LR, pivot=median of 3) | Quick sort (LR, pivot=median of 9) | Quick sort (LR, pivot=random) | Quick sort (LL, pivot=first) | Quick sort (LL, pivot=last) | Quick sort (LL, pivot=middle) | Quick sort (LL, pivot=median of 3) | Quick sort (LL, pivot=median of 9) | Quick sort (LL, pivot=random) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1024(random) | \(0.043\text{ms}(12641)\) | \(0.070\text{ms}(9985)\) | \(0.062\text{ms}(15070)\) | \(0.071\text{ms}(13878)\) | \(0.193\text{ms}(265364)\) | \(0.394\text{ms}(523776)\) | \(1.008\text{ms}(519395)\) | \(0.835\text{ms}(357318)\) | \(0.991\text{ms}(529712)\) | \(0.063\text{ms}(23260)\) | \(0.182\text{ms}(8932)\) | \(0.079\text{ms}(10601)\) | \(0.118\text{ms}(22626)\) | \(0.057\text{ms}(12808)\) | \(0.252\text{ms}(28160)\) | \(0.094\text{ms}(13653)\) | \(0.061\text{ms}(13238)\) | \(0.054\text{ms}(12784)\) | \(0.052\text{ms}(12635)\) | \(0.174\text{ms}(25923)\) | \(0.064\text{ms}(11464)\) | \(0.049\text{ms}(10518)\) | \(0.069\text{ms}(11674)\) | \(0.052\text{ms}(10455)\) | \(0.050\text{ms}(11575)\) | \(0.136\text{ms}(20132)\) | \(0.075\text{ms}(10162)\) |
| 1024(ascending) | \(0.009\text{ms}(10899)\) | \(0.011\text{ms}(6142)\) | \(0.003\text{ms}(1023)\) | \(0.002\text{ms}(1023)\) | \(0.002\text{ms}(1023)\) | \(0.584\text{ms}(523776)\) | \(0.003\text{ms}(1023)\) | \(0.001\text{ms}(1023)\) | \(0.002\text{ms}(1023)\) | \(0.001\text{ms}(237)\) | \(0.098\text{ms}(5120)\) | \(0.053\text{ms}(10654)\) | \(0.010\text{ms}(2029)\) | \(0.009\text{ms}(5380)\) | \(0.122\text{ms}(28160)\) | \(0.333\text{ms}(524797)\) | \(0.237\text{ms}(262654)\) | \(0.010\text{ms}(8714)\) | \(0.010\text{ms}(10247)\) | \(0.090\text{ms}(22009)\) | \(0.030\text{ms}(12324)\) | \(0.320\text{ms}(262655)\) | \(0.277\text{ms}(262143)\) | \(0.015\text{ms}(8149)\) | \(0.037\text{ms}(22656)\) | \(0.095\text{ms}(19403)\) | \(0.046\text{ms}(11230)\) |
| 1024(descending) | \(0.007\text{ms}(8330)\) | \(0.014\text{ms}(4390)\) | \(0.003\text{ms}(1023)\) | \(0.001\text{ms}(1023)\) | \(0.386\text{ms}(523776)\) | \(0.334\text{ms}(523776)\) | \(0.720\text{ms}(523776)\) | \(0.882\text{ms}(524799)\) | \(1.932\text{ms}(1047552)\) | \(0.001\text{ms}(656)\) | \(0.089\text{ms}(5120)\) | \(0.060\text{ms}(11053)\) | \(0.072\text{ms}(20113)\) | \(0.017\text{ms}(9092)\) | \(0.121\text{ms}(28160)\) | \(0.219\text{ms}(350205)\) | \(0.219\text{ms}(350548)\) | \(0.011\text{ms}(8714)\) | \(0.011\text{ms}(10247)\) | \(0.058\text{ms}(22013)\) | \(0.031\text{ms}(10806)\) | \(0.419\text{ms}(262143)\) | \(0.370\text{ms}(349525)\) | \(0.016\text{ms}(8241)\) | \(0.030\text{ms}(16103)\) | \(0.059\text{ms}(20405)\) | \(0.036\text{ms}(10849)\) |
| 1024(pipe organ) | \(0.063\text{ms}(24324)\) | \(0.014\text{ms}(5777)\) | \(0.005\text{ms}(2046)\) | \(0.006\text{ms}(2557)\) | \(0.186\text{ms}(263166)\) | \(0.381\text{ms}(523776)\) | \(0.708\text{ms}(523776)\) | \(0.535\text{ms}(350888)\) | \(0.973\text{ms}(525310)\) | \(0.027\text{ms}(20191)\) | \(0.088\text{ms}(5631)\) | \(0.058\text{ms}(10693)\) | \(0.076\text{ms}(22679)\) | \(0.016\text{ms}(7903)\) | \(0.137\text{ms}(28160)\) | \(0.041\text{ms}(27950)\) | \(0.040\text{ms}(30858)\) | \(0.048\text{ms}(37135)\) | \(0.044\text{ms}(24018)\) | \(0.091\text{ms}(24959)\) | \(0.053\text{ms}(12298)\) | \(0.162\text{ms}(96087)\) | \(0.072\text{ms}(54145)\) | \(0.058\text{ms}(34294)\) | \(0.051\text{ms}(28689)\) | \(0.076\text{ms}(20041)\) | \(0.037\text{ms}(10824)\) |
| 1024(final merge) | \(0.007\text{ms}(8332)\) | \(0.011\text{ms}(6142)\) | \(0.004\text{ms}(1535)\) | \(0.009\text{ms}(2046)\) | \(0.186\text{ms}(263166)\) | \(0.328\text{ms}(523776)\) | \(0.538\text{ms}(393471)\) | \(0.817\text{ms}(524799)\) | \(0.945\text{ms}(525310)\) | \(0.030\text{ms}(20191)\) | \(0.089\text{ms}(5120)\) | \(0.058\text{ms}(11054)\) | \(0.077\text{ms}(18426)\) | \(0.010\text{ms}(5380)\) | \(0.120\text{ms}(28160)\) | \(0.121\text{ms}(176465)\) | \(0.120\text{ms}(176807)\) | \(0.181\text{ms}(263163)\) | \(0.013\text{ms}(11565)\) | \(0.059\text{ms}(22058)\) | \(0.033\text{ms}(12517)\) | \(0.171\text{ms}(132348)\) | \(0.215\text{ms}(131583)\) | \(0.355\text{ms}(262143)\) | \(0.040\text{ms}(23395)\) | \(0.062\text{ms}(19341)\) | \(0.034\text{ms}(9965)\) |
| 1024(final merge reversed) | \(0.052\text{ms}(25037)\) | \(0.014\text{ms}(4901)\) | \(0.004\text{ms}(2046)\) | \(0.005\text{ms}(2557)\) | \(0.278\text{ms}(393471)\) | \(0.382\text{ms}(523776)\) | \(0.718\text{ms}(523776)\) | \(0.775\text{ms}(466488)\) | \(1.482\text{ms}(786431)\) | \(0.001\text{ms}(656)\) | \(0.089\text{ms}(5631)\) | \(0.058\text{ms}(11005)\) | \(0.098\text{ms}(23826)\) | \(0.020\text{ms}(11020)\) | \(0.140\text{ms}(28160)\) | \(0.044\text{ms}(30278)\) | \(0.041\text{ms}(25748)\) | \(0.051\text{ms}(36666)\) | \(0.043\text{ms}(23805)\) | \(0.094\text{ms}(25720)\) | \(0.050\text{ms}(13693)\) | \(0.259\text{ms}(180735)\) | \(0.116\text{ms}(107097)\) | \(0.441\text{ms}(390923)\) | \(0.097\text{ms}(91379)\) | \(0.077\text{ms}(19691)\) | \(0.040\text{ms}(11648)\) |
| 1024(heapified) | \(0.032\text{ms}(12635)\) | \(0.031\text{ms}(9097)\) | \(0.034\text{ms}(11897)\) | \(0.043\text{ms}(13123)\) | \(0.239\text{ms}(343244)\) | \(0.437\text{ms}(523776)\) | \(0.804\text{ms}(523348)\) | \(0.753\text{ms}(455353)\) | \(1.256\text{ms}(685483)\) | \(0.055\text{ms}(22237)\) | \(0.103\text{ms}(8028)\) | \(0.054\text{ms}(11157)\) | \(0.083\text{ms}(21162)\) | \(0.051\text{ms}(10922)\) | \(0.205\text{ms}(28160)\) | \(0.050\text{ms}(17229)\) | \(0.046\text{ms}(17033)\) | \(0.048\text{ms}(11115)\) | \(0.047\text{ms}(12368)\) | \(0.125\text{ms}(25922)\) | \(0.060\text{ms}(12746)\) | \(0.043\text{ms}(14792)\) | \(0.044\text{ms}(16914)\) | \(0.047\text{ms}(11016)\) | \(0.039\text{ms}(11012)\) | \(0.102\text{ms}(20122)\) | \(0.048\text{ms}(11858)\) |
| 1024(binary search tree) | \(0.030\text{ms}(16070)\) | \(0.015\text{ms}(7450)\) | \(0.008\text{ms}(3184)\) | \(0.040\text{ms}(14908)\) | \(0.127\text{ms}(176287)\) | \(0.352\text{ms}(523776)\) | \(0.357\text{ms}(262655)\) | \(0.475\text{ms}(290954)\) | \(0.656\text{ms}(351561)\) | \(0.046\text{ms}(22237)\) | \(0.095\text{ms}(6133)\) | \(0.051\text{ms}(10218)\) | \(0.082\text{ms}(22586)\) | \(0.034\text{ms}(10206)\) | \(0.141\text{ms}(28160)\) | \(0.045\text{ms}(23687)\) | \(0.039\text{ms}(21237)\) | \(0.040\text{ms}(16679)\) | \(0.042\text{ms}(17478)\) | \(0.123\text{ms}(31191)\) | \(0.052\text{ms}(11708)\) | \(0.027\text{ms}(9984)\) | \(0.157\text{ms}(131840)\) | \(0.067\text{ms}(41984)\) | \(0.158\text{ms}(133626)\) | \(0.088\text{ms}(22223)\) | \(0.043\text{ms}(12615)\) |
| 1024(sawtooth) | \(0.031\text{ms}(11828)\) | \(0.018\text{ms}(9580)\) | \(0.029\text{ms}(12032)\) | \(0.046\text{ms}(13186)\) | \(0.141\text{ms}(196863)\) | \(0.345\text{ms}(523776)\) | \(0.684\text{ms}(489093)\) | \(0.425\text{ms}(311169)\) | \(0.791\text{ms}(392703)\) | \(0.008\text{ms}(7092)\) | \(0.100\text{ms}(8192)\) | \(0.062\text{ms}(10510)\) | \(0.083\text{ms}(21987)\) | \(0.014\text{ms}(7938)\) | \(0.130\text{ms}(28160)\) | \(0.044\text{ms}(15563)\) | \(0.040\text{ms}(15061)\) | \(0.049\text{ms}(12510)\) | \(0.041\text{ms}(11673)\) | \(0.110\text{ms}(25532)\) | \(0.055\text{ms}(12432)\) | \(0.055\text{ms}(27972)\) | \(0.049\text{ms}(26103)\) | \(0.038\text{ms}(14647)\) | \(0.035\text{ms}(11590)\) | \(0.087\text{ms}(19992)\) | \(0.041\text{ms}(10295)\) |
| 1024(scrambled head) | \(0.025\text{ms}(13041)\) | \(0.018\text{ms}(7097)\) | \(0.011\text{ms}(4310)\) | \(0.030\text{ms}(10619)\) | \(0.124\text{ms}(159871)\) | \(0.349\text{ms}(523776)\) | \(0.686\text{ms}(514541)\) | \(0.353\text{ms}(228298)\) | \(0.580\text{ms}(318721)\) | \(0.051\text{ms}(23260)\) | \(0.095\text{ms}(6266)\) | \(0.058\text{ms}(10754)\) | \(0.089\text{ms}(20274)\) | \(0.042\text{ms}(10593)\) | \(0.150\text{ms}(28160)\) | \(0.037\text{ms}(17270)\) | \(0.036\text{ms}(21502)\) | \(0.038\text{ms}(19711)\) | \(0.037\text{ms}(11633)\) | \(0.113\text{ms}(25131)\) | \(0.049\text{ms}(12123)\) | \(0.033\text{ms}(14901)\) | \(0.044\text{ms}(25298)\) | \(0.052\text{ms}(34952)\) | \(0.032\text{ms}(11603)\) | \(0.089\text{ms}(19790)\) | \(0.040\text{ms}(10736)\) |
| 1024(scrambled tail) | \(0.028\text{ms}(15439)\) | \(0.016\text{ms}(6624)\) | \(0.009\text{ms}(3422)\) | \(0.009\text{ms}(3296)\) | \(0.044\text{ms}(62337)\) | \(0.352\text{ms}(523776)\) | \(0.739\text{ms}(523520)\) | \(0.195\text{ms}(117627)\) | \(0.236\text{ms}(123651)\) | \(0.050\text{ms}(21214)\) | \(0.095\text{ms}(5699)\) | \(0.057\text{ms}(10648)\) | \(0.073\text{ms}(18474)\) | \(0.042\text{ms}(9781)\) | \(0.140\text{ms}(28160)\) | \(0.054\text{ms}(47096)\) | \(0.065\text{ms}(61876)\) | \(0.071\text{ms}(19619)\) | \(0.039\text{ms}(12706)\) | \(0.098\text{ms}(23990)\) | \(0.050\text{ms}(12385)\) | \(0.068\text{ms}(38646)\) | \(0.068\text{ms}(48375)\) | \(0.041\text{ms}(18688)\) | \(0.048\text{ms}(25059)\) | \(0.083\text{ms}(19670)\) | \(0.045\text{ms}(11742)\) |
| 1024(half-reversed) | \(0.037\text{ms}(20739)\) | \(0.014\text{ms}(5266)\) | \(0.004\text{ms}(1535)\) | \(0.004\text{ms}(2045)\) | \(0.096\text{ms}(131839)\) | \(0.352\text{ms}(523776)\) | \(0.530\text{ms}(392960)\) | \(0.248\text{ms}(132351)\) | \(0.487\text{ms}(262655)\) | \(0.001\text{ms}(237)\) | \(0.110\text{ms}(5120)\) | \(0.053\text{ms}(10612)\) | \(0.044\text{ms}(11316)\) | \(0.013\text{ms}(7480)\) | \(0.121\text{ms}(28160)\) | \(0.306\text{ms}(481192)\) | \(0.112\text{ms}(154450)\) | \(0.010\text{ms}(8714)\) | \(0.010\text{ms}(10247)\) | \(0.058\text{ms}(22010)\) | \(0.031\text{ms}(11240)\) | \(0.376\text{ms}(262400)\) | \(0.176\text{ms}(153427)\) | \(0.018\text{ms}(8191)\) | \(0.033\text{ms}(15839)\) | \(0.063\text{ms}(19875)\) | \(0.035\text{ms}(10754)\) |
| 1024(adversary) | \(0.015\text{ms}(9645)\) | \(0.017\text{ms}(8053)\) | \(0.025\text{ms}(6161)\) | \(0.025\text{ms}(9369)\) | \(0.214\text{ms}(306090)\) | \(0.359\text{ms}(523776)\) | \(0.536\text{ms}(392960)\) | \(0.791\text{ms}(523776)\) | \(1.130\text{ms}(611157)\) | \(0.033\text{ms}(23260)\) | \(0.095\text{ms}(6914)\) | \(0.039\text{ms}(10231)\) | \(0.054\text{ms}(14671)\) | \(0.014\text{ms}(6117)\) | \(0.138\text{ms}(28160)\) | \(0.026\text{ms}(12695)\) | \(0.025\text{ms}(15640)\) | \(0.026\text{ms}(11670)\) | \(0.025\text{ms}(11013)\) | \(0.082\text{ms}(20927)\) | \(0.036\text{ms}(10498)\) | \(0.198\text{ms}(151379)\) | \(0.281\text{ms}(168246)\) | \(0.267\text{ms}(296161)\) | \(0.473\text{ms}(526841)\) | \(0.218\text{ms}(150468)\) | \(0.172\text{ms}(154323)\) |
| \(\;\) | |||||||||||||||||||||||||||
| 16384(random) | \(0.869\text{ms}(273405)\) | \(1.142\text{ms}(226030)\) | \(1.211\text{ms}(345310)\) | \(1.058\text{ms}(312517)\) | \(48.338\text{ms}(67175004)\) | \(84.215\text{ms}(134209536)\) | \(377.773\text{ms}(134178290)\) | \(290.775\text{ms}(89652688)\) | \(238.980\text{ms}(134333632)\) | \(1.543\text{ms}(617194)\) | \(2.335\text{ms}(208685)\) | \(1.496\text{ms}(235143)\) | \(1.939\text{ms}(573752)\) | \(1.663\text{ms}(446532)\) | \(5.035\text{ms}(860160)\) | \(1.095\text{ms}(310841)\) | \(1.028\text{ms}(305324)\) | \(1.047\text{ms}(293550)\) | \(1.263\text{ms}(274760)\) | \(2.262\text{ms}(488197)\) | \(1.246\text{ms}(282719)\) | \(0.986\text{ms}(267205)\) | \(0.977\text{ms}(262651)\) | \(0.966\text{ms}(277347)\) | \(1.005\text{ms}(243492)\) | \(1.905\text{ms}(403307)\) | \(1.116\text{ms}(260391)\) |
| 16384(ascending) | \(0.160\text{ms}(272411)\) | \(0.237\text{ms}(131070)\) | \(0.012\text{ms}(16383)\) | \(0.025\text{ms}(16383)\) | \(0.028\text{ms}(16383)\) | \(82.542\text{ms}(134209536)\) | \(0.021\text{ms}(16383)\) | \(0.023\text{ms}(16383)\) | \(0.030\text{ms}(16383)\) | \(0.004\text{ms}(3781)\) | \(1.411\text{ms}(114688)\) | \(0.896\text{ms}(236485)\) | \(0.126\text{ms}(32743)\) | \(0.266\text{ms}(135172)\) | \(1.980\text{ms}(860160)\) | \(81.785\text{ms}(134225917)\) | \(41.257\text{ms}(67117054)\) | \(0.172\text{ms}(204814)\) | \(0.172\text{ms}(229387)\) | \(0.914\text{ms}(417793)\) | \(0.481\text{ms}(262587)\) | \(81.152\text{ms}(67117055)\) | \(71.805\text{ms}(67108863)\) | \(0.285\text{ms}(195745)\) | \(1.506\text{ms}(1346728)\) | \(0.963\text{ms}(385782)\) | \(0.559\text{ms}(255083)\) |
| 16384(descending) | \(0.134\text{ms}(198666)\) | \(0.267\text{ms}(102988)\) | \(0.018\text{ms}(16383)\) | \(0.016\text{ms}(16383)\) | \(92.893\text{ms}(134209536)\) | \(86.406\text{ms}(134209536)\) | \(186.139\text{ms}(134209536)\) | \(219.323\text{ms}(134225919)\) | \(500.478\text{ms}(268419072)\) | \(0.010\text{ms}(10471)\) | \(2.028\text{ms}(114688)\) | \(1.041\text{ms}(242159)\) | \(1.253\text{ms}(460904)\) | \(0.412\text{ms}(245822)\) | \(2.066\text{ms}(860160)\) | \(57.938\text{ms}(89489405)\) | \(61.424\text{ms}(89494868)\) | \(0.178\text{ms}(204814)\) | \(0.210\text{ms}(229387)\) | \(0.935\text{ms}(417797)\) | \(0.512\text{ms}(273011)\) | \(113.454\text{ms}(67108863)\) | \(117.257\text{ms}(89478485)\) | \(0.351\text{ms}(197246)\) | \(0.614\text{ms}(462959)\) | \(1.137\text{ms}(395480)\) | \(0.766\text{ms}(264304)\) |
| 16384(pipe organ) | \(1.467\text{ms}(638262)\) | \(0.277\text{ms}(125220)\) | \(0.069\text{ms}(32766)\) | \(0.111\text{ms}(40957)\) | \(54.273\text{ms}(67125246)\) | \(102.061\text{ms}(134209536)\) | \(201.656\text{ms}(134209536)\) | \(153.588\text{ms}(89500328)\) | \(314.204\text{ms}(134234110)\) | \(0.831\text{ms}(502513)\) | \(1.904\text{ms}(122879)\) | \(1.257\text{ms}(237860)\) | \(1.938\text{ms}(576331)\) | \(0.435\text{ms}(202217)\) | \(2.557\text{ms}(860160)\) | \(1.028\text{ms}(865169)\) | \(1.049\text{ms}(967904)\) | \(2.173\text{ms}(2254818)\) | \(1.312\text{ms}(700809)\) | \(1.537\text{ms}(466873)\) | \(0.937\text{ms}(293457)\) | \(42.283\text{ms}(22574423)\) | \(16.216\text{ms}(11418225)\) | \(2.946\text{ms}(2106422)\) | \(7.548\text{ms}(6117283)\) | \(1.087\text{ms}(386456)\) | \(0.641\text{ms}(262698)\) |
| 16384(final merge) | \(0.142\text{ms}(198668)\) | \(0.238\text{ms}(131070)\) | \(0.047\text{ms}(24575)\) | \(0.086\text{ms}(32766)\) | \(50.884\text{ms}(67125246)\) | \(96.169\text{ms}(134209536)\) | \(201.151\text{ms}(100667391)\) | \(225.122\text{ms}(134225919)\) | \(280.666\text{ms}(134234110)\) | \(0.770\text{ms}(502513)\) | \(1.550\text{ms}(114688)\) | \(1.101\text{ms}(243517)\) | \(1.197\text{ms}(417125)\) | \(0.258\text{ms}(135172)\) | \(2.105\text{ms}(860160)\) | \(31.164\text{ms}(44766545)\) | \(31.688\text{ms}(44772007)\) | \(50.273\text{ms}(67125243)\) | \(0.264\text{ms}(253525)\) | \(0.989\text{ms}(417866)\) | \(0.641\text{ms}(262483)\) | \(48.212\text{ms}(33574908)\) | \(42.214\text{ms}(33562623)\) | \(99.946\text{ms}(67108863)\) | \(1.756\text{ms}(1362125)\) | \(1.114\text{ms}(383684)\) | \(0.676\text{ms}(256719)\) |
| 16384(final merge reversed) | \(1.304\text{ms}(625996)\) | \(0.305\text{ms}(111179)\) | \(0.053\text{ms}(32766)\) | \(0.115\text{ms}(40957)\) | \(114.136\text{ms}(100667391)\) | \(101.498\text{ms}(134209536)\) | \(226.645\text{ms}(134209536)\) | \(230.679\text{ms}(119311928)\) | \(442.340\text{ms}(201326591)\) | \(0.016\text{ms}(10471)\) | \(1.580\text{ms}(122879)\) | \(1.210\text{ms}(242696)\) | \(1.963\text{ms}(597224)\) | \(0.599\text{ms}(298632)\) | \(2.606\text{ms}(860160)\) | \(1.143\text{ms}(1024757)\) | \(0.974\text{ms}(801618)\) | \(1.743\text{ms}(1432379)\) | \(0.916\text{ms}(664214)\) | \(1.631\text{ms}(475112)\) | \(0.929\text{ms}(276722)\) | \(86.519\text{ms}(46145535)\) | \(50.690\text{ms}(26879577)\) | \(207.739\text{ms}(100626443)\) | \(50.560\text{ms}(22433779)\) | \(1.814\text{ms}(383042)\) | \(0.985\text{ms}(262551)\) |
| 16384(heapified) | \(0.936\text{ms}(281663)\) | \(0.617\text{ms}(195499)\) | \(0.578\text{ms}(242015)\) | \(0.922\text{ms}(285064)\) | \(72.566\text{ms}(86564745)\) | \(102.179\text{ms}(134209536)\) | \(240.136\text{ms}(134202877)\) | \(221.239\text{ms}(115833739)\) | \(356.537\text{ms}(173113132)\) | \(1.716\text{ms}(600811)\) | \(1.601\text{ms}(178071)\) | \(1.259\text{ms}(244664)\) | \(1.838\text{ms}(498317)\) | \(1.520\text{ms}(370531)\) | \(4.335\text{ms}(860160)\) | \(0.990\text{ms}(436577)\) | \(1.004\text{ms}(464902)\) | \(1.039\text{ms}(258870)\) | \(1.018\text{ms}(279555)\) | \(2.229\text{ms}(484164)\) | \(1.302\text{ms}(290579)\) | \(1.152\text{ms}(368091)\) | \(4.065\text{ms}(2004307)\) | \(1.091\text{ms}(414175)\) | \(0.883\text{ms}(256039)\) | \(2.049\text{ms}(396232)\) | \(1.011\text{ms}(256779)\) |
| 16384(binary search tree) | \(0.784\text{ms}(418939)\) | \(0.301\text{ms}(152126)\) | \(0.090\text{ms}(49260)\) | \(0.732\text{ms}(307859)\) | \(41.099\text{ms}(44763803)\) | \(152.853\text{ms}(134209536)\) | \(126.134\text{ms}(67117055)\) | \(145.696\text{ms}(74116422)\) | \(211.301\text{ms}(89511237)\) | \(1.262\text{ms}(568045)\) | \(1.568\text{ms}(131057)\) | \(1.200\text{ms}(227871)\) | \(1.962\text{ms}(572347)\) | \(0.950\text{ms}(284229)\) | \(2.461\text{ms}(860160)\) | \(1.051\text{ms}(685658)\) | \(1.037\text{ms}(584474)\) | \(0.998\text{ms}(472348)\) | \(0.896\text{ms}(444253)\) | \(2.329\text{ms}(640082)\) | \(1.103\text{ms}(282181)\) | \(0.738\text{ms}(253260)\) | \(49.008\text{ms}(33566720)\) | \(3.288\text{ms}(2587004)\) | \(48.909\text{ms}(33595386)\) | \(1.604\text{ms}(429593)\) | \(0.848\text{ms}(245834)\) |
| 16384(sawtooth) | \(0.734\text{ms}(266483)\) | \(0.383\text{ms}(210654)\) | \(0.474\text{ms}(273952)\) | \(0.897\text{ms}(295452)\) | \(42.852\text{ms}(50335743)\) | \(102.813\text{ms}(134209536)\) | \(286.825\text{ms}(125790213)\) | \(138.987\text{ms}(79689729)\) | \(213.257\text{ms}(100655103)\) | \(0.022\text{ms}(19399)\) | \(1.732\text{ms}(188416)\) | \(1.395\text{ms}(234076)\) | \(1.871\text{ms}(566593)\) | \(0.592\text{ms}(259891)\) | \(2.859\text{ms}(860160)\) | \(1.187\text{ms}(380851)\) | \(1.506\text{ms}(616866)\) | \(1.902\text{ms}(295964)\) | \(2.074\text{ms}(262617)\) | \(4.570\text{ms}(470378)\) | \(2.418\text{ms}(279580)\) | \(20.432\text{ms}(4876814)\) | \(23.024\text{ms}(4432662)\) | \(11.184\text{ms}(4107812)\) | \(3.504\text{ms}(384368)\) | \(6.597\text{ms}(394983)\) | \(3.075\text{ms}(256834)\) |
| 16384(scrambled head) | \(2.345\text{ms}(270474)\) | \(1.486\text{ms}(150952)\) | \(0.453\text{ms}(78781)\) | \(1.427\text{ms}(213225)\) | \(67.737\text{ms}(40918396)\) | \(153.001\text{ms}(134209536)\) | \(332.154\text{ms}(131814838)\) | \(104.598\text{ms}(58322596)\) | \(193.058\text{ms}(81820413)\) | \(1.728\text{ms}(600811)\) | \(1.899\text{ms}(137364)\) | \(1.293\text{ms}(237974)\) | \(1.883\text{ms}(537613)\) | \(1.839\text{ms}(356490)\) | \(5.955\text{ms}(860160)\) | \(1.057\text{ms}(470716)\) | \(1.072\text{ms}(683873)\) | \(3.128\text{ms}(3301625)\) | \(0.831\text{ms}(263876)\) | \(2.072\text{ms}(465402)\) | \(1.124\text{ms}(284782)\) | \(1.061\text{ms}(387321)\) | \(4.702\text{ms}(3148382)\) | \(10.180\text{ms}(7636400)\) | \(0.868\text{ms}(263357)\) | \(1.683\text{ms}(382817)\) | \(0.907\text{ms}(265407)\) |
| 16384(scrambled tail) | \(0.760\text{ms}(442079)\) | \(0.492\text{ms}(143882)\) | \(0.169\text{ms}(64453)\) | \(0.177\text{ms}(64529)\) | \(14.325\text{ms}(15764864)\) | \(101.786\text{ms}(134209536)\) | \(216.539\text{ms}(134189762)\) | \(61.050\text{ms}(29574367)\) | \(96.701\text{ms}(31513345)\) | \(1.601\text{ms}(584428)\) | \(1.814\text{ms}(128295)\) | \(1.200\text{ms}(235995)\) | \(1.766\text{ms}(511091)\) | \(1.462\text{ms}(336460)\) | \(2.995\text{ms}(860160)\) | \(1.581\text{ms}(1355051)\) | \(0.936\text{ms}(679289)\) | \(2.869\text{ms}(3398237)\) | \(0.731\text{ms}(261375)\) | \(2.095\text{ms}(466367)\) | \(1.062\text{ms}(284174)\) | \(2.193\text{ms}(1185220)\) | \(1.155\text{ms}(603408)\) | \(4.676\text{ms}(3421392)\) | \(0.679\text{ms}(310601)\) | \(1.341\text{ms}(387185)\) | \(0.746\text{ms}(268343)\) |
| 16384(half-reversed) | \(0.823\text{ms}(488862)\) | \(0.418\text{ms}(117029)\) | \(0.037\text{ms}(24575)\) | \(0.072\text{ms}(32765)\) | \(29.020\text{ms}(33566719)\) | \(104.806\text{ms}(134209536)\) | \(198.847\text{ms}(100659200)\) | \(66.715\text{ms}(33574911)\) | \(207.096\text{ms}(67117055)\) | \(0.004\text{ms}(3781)\) | \(1.515\text{ms}(114688)\) | \(1.035\text{ms}(236807)\) | \(0.693\text{ms}(239172)\) | \(0.354\text{ms}(194576)\) | \(2.397\text{ms}(860160)\) | \(92.228\text{ms}(123042472)\) | \(36.833\text{ms}(39171410)\) | \(0.341\text{ms}(204814)\) | \(0.402\text{ms}(229387)\) | \(2.686\text{ms}(417794)\) | \(1.095\text{ms}(269198)\) | \(151.400\text{ms}(67112960)\) | \(49.283\text{ms}(39155027)\) | \(0.326\text{ms}(196506)\) | \(0.983\text{ms}(703973)\) | \(1.470\text{ms}(389123)\) | \(1.125\text{ms}(255972)\) |
| 16384(adversary) | \(0.342\text{ms}(223881)\) | \(0.328\text{ms}(178027)\) | \(0.270\text{ms}(139062)\) | \(0.461\text{ms}(171697)\) | \(80.011\text{ms}(78297770)\) | \(134.257\text{ms}(134209536)\) | \(218.098\text{ms}(100659200)\) | \(230.928\text{ms}(134209536)\) | \(500.174\text{ms}(156579157)\) | \(0.858\text{ms}(649960)\) | \(1.544\text{ms}(159746)\) | \(0.762\text{ms}(229276)\) | \(1.101\text{ms}(339666)\) | \(0.414\text{ms}(191661)\) | \(3.058\text{ms}(860160)\) | \(0.544\text{ms}(306543)\) | \(1.541\text{ms}(1682034)\) | \(0.790\text{ms}(264744)\) | \(0.506\text{ms}(247225)\) | \(1.466\text{ms}(398444)\) | \(0.813\text{ms}(240217)\) | \(55.384\text{ms}(37833275)\) | \(61.936\text{ms}(42150967)\) | \(91.850\text{ms}(75546639)\) | \(302.622\text{ms}(134258681)\) | \(76.394\text{ms}(33900120)\) | \(62.637\text{ms}(34712211)\) |
| \(\;\) | |||||||||||||||||||||||||||
| 131072(random) | \(13.131\text{ms}(2639511)\) | \(15.335\text{ms}(2203088)\) | \(16.691\text{ms}(3338447)\) | \(18.325\text{ms}(2841361)\) | \(3560.487\text{ms}(4294035285)\) | \(5865.733\text{ms}(8589869056)\) | \(31307.700\text{ms}(8589456381)\) | \(22290.987\text{ms}(5722066232)\) | \(15918.790\text{ms}(8587939507)\) | \(14.706\text{ms}(5461420)\) | \(19.694\text{ms}(2062729)\) | \(15.012\text{ms}(2274391)\) | \(19.509\text{ms}(5872698)\) | \(19.738\text{ms}(5819771)\) | \(54.738\text{ms}(10027008)\) | \(10.694\text{ms}(3172349)\) | \(9.923\text{ms}(3143883)\) | \(10.429\text{ms}(2783755)\) | \(10.327\text{ms}(2647945)\) | \(19.579\text{ms}(4410192)\) | \(11.570\text{ms}(2873342)\) | \(9.793\text{ms}(2657616)\) | \(9.752\text{ms}(2587712)\) | \(9.779\text{ms}(2646900)\) | \(9.605\text{ms}(2602579)\) | \(17.265\text{ms}(3636117)\) | \(11.009\text{ms}(2659061)\) |
| 131072(ascending) | \(1.667\text{ms}(2768929)\) | \(1.866\text{ms}(1245182)\) | \(0.090\text{ms}(131071)\) | \(0.220\text{ms}(131071)\) | \(0.271\text{ms}(131071)\) | \(5250.243\text{ms}(8589869056)\) | \(0.167\text{ms}(131071)\) | \(0.123\text{ms}(131071)\) | \(0.232\text{ms}(131071)\) | \(0.029\text{ms}(30248)\) | \(10.741\text{ms}(1114112)\) | \(7.383\text{ms}(2283581)\) | \(1.031\text{ms}(262113)\) | \(2.203\text{ms}(1343494)\) | \(20.558\text{ms}(10027008)\) | \(5751.980\text{ms}(8590000125)\) | \(3013.977\text{ms}(4295032830)\) | \(1.785\text{ms}(2031633)\) | \(1.974\text{ms}(2228238)\) | \(10.341\text{ms}(3735559)\) | \(4.942\text{ms}(2921005)\) | \(6275.986\text{ms}(4295032831)\) | \(5594.626\text{ms}(4294967295)\) | \(3.100\text{ms}(1959076)\) | \(33.458\text{ms}(29558583)\) | \(8.601\text{ms}(3537076)\) | \(6.458\text{ms}(2677870)\) |
| 131072(descending) | \(1.415\text{ms}(1982474)\) | \(2.331\text{ms}(1020492)\) | \(0.138\text{ms}(131071)\) | \(0.134\text{ms}(131071)\) | \(6904.255\text{ms}(8589869056)\) | \(6446.063\text{ms}(8589869056)\) | \(13945.832\text{ms}(8589869056)\) | \(16041.752\text{ms}(8590000127)\) | \(36044.323\text{ms}(17179738112)\) | \(0.092\text{ms}(83764)\) | \(10.956\text{ms}(1114112)\) | \(8.701\text{ms}(2337036)\) | \(11.416\text{ms}(4475879)\) | \(4.769\text{ms}(2458234)\) | \(23.046\text{ms}(10027008)\) | \(4397.927\text{ms}(5726710440)\) | \(4183.762\text{ms}(5726754130)\) | \(2.284\text{ms}(2031633)\) | \(1.808\text{ms}(2228238)\) | \(9.287\text{ms}(3735563)\) | \(5.275\text{ms}(3196336)\) | \(7096.338\text{ms}(4294967295)\) | \(7222.475\text{ms}(5726623060)\) | \(3.147\text{ms}(1970781)\) | \(8.242\text{ms}(5015574)\) | \(10.795\text{ms}(3581498)\) | \(7.387\text{ms}(2592741)\) |
| 131072(pipe organ) | \(13.630\text{ms}(6465407)\) | \(2.759\text{ms}(1198372)\) | \(0.461\text{ms}(262142)\) | \(0.739\text{ms}(327677)\) | \(3795.289\text{ms}(4295098366)\) | \(7272.228\text{ms}(8589869056)\) | \(13479.140\text{ms}(8589869056)\) | \(10312.043\text{ms}(5726797822)\) | \(17400.462\text{ms}(8590065662)\) | \(6.716\text{ms}(5068207)\) | \(23.068\text{ms}(1179647)\) | \(10.450\text{ms}(2300431)\) | \(17.356\text{ms}(5915619)\) | \(4.070\text{ms}(1998901)\) | \(26.399\text{ms}(10027008)\) | \(11.970\text{ms}(10201169)\) | \(13.516\text{ms}(11425050)\) | \(63.845\text{ms}(49580731)\) | \(24.980\text{ms}(7876485)\) | \(34.683\text{ms}(4191298)\) | \(21.561\text{ms}(2737712)\) | \(2410.989\text{ms}(1433687383)\) | \(806.950\text{ms}(718088805)\) | \(59.377\text{ms}(46491921)\) | \(490.642\text{ms}(401109415)\) | \(8.881\text{ms}(3490389)\) | \(7.787\text{ms}(2811900)\) |
| 131072(final merge) | \(1.556\text{ms}(1982476)\) | \(2.176\text{ms}(1245182)\) | \(0.390\text{ms}(196607)\) | \(0.631\text{ms}(262142)\) | \(3285.796\text{ms}(4295098366)\) | \(5767.009\text{ms}(8589869056)\) | \(9776.981\text{ms}(6442483711)\) | \(14726.550\text{ms}(8590000127)\) | \(16754.675\text{ms}(8590065662)\) | \(6.280\text{ms}(5068207)\) | \(10.565\text{ms}(1114112)\) | \(8.381\text{ms}(2339980)\) | \(10.169\text{ms}(4111575)\) | \(2.459\text{ms}(1343494)\) | \(21.730\text{ms}(10027008)\) | \(1846.689\text{ms}(2863529980)\) | \(1849.141\text{ms}(2863573669)\) | \(2829.219\text{ms}(4295098363)\) | \(1.964\text{ms}(2424201)\) | \(7.972\text{ms}(3735650)\) | \(4.833\text{ms}(2712569)\) | \(3008.168\text{ms}(2147647484)\) | \(2597.166\text{ms}(2147549183)\) | \(5669.601\text{ms}(4294967295)\) | \(35.192\text{ms}(29689369)\) | \(9.326\text{ms}(3518320)\) | \(5.770\text{ms}(2613544)\) |
| 131072(final merge reversed) | \(12.537\text{ms}(6321560)\) | \(2.719\text{ms}(1086027)\) | \(0.410\text{ms}(262142)\) | \(0.624\text{ms}(327677)\) | \(5125.468\text{ms}(6442483711)\) | \(6415.716\text{ms}(8589869056)\) | \(13627.847\text{ms}(8589869056)\) | \(13755.536\text{ms}(7635570232)\) | \(25793.912\text{ms}(12884901887)\) | \(0.089\text{ms}(83764)\) | \(10.794\text{ms}(1179647)\) | \(10.094\text{ms}(2337227)\) | \(15.541\text{ms}(6077913)\) | \(5.210\text{ms}(3009191)\) | \(22.988\text{ms}(10027008)\) | \(11.624\text{ms}(11780206)\) | \(11.845\text{ms}(9567114)\) | \(65.939\text{ms}(63922573)\) | \(12.208\text{ms}(7592421)\) | \(18.821\text{ms}(4128200)\) | \(15.651\text{ms}(2792602)\) | \(4627.641\text{ms}(2952855551)\) | \(2040.151\text{ms}(1718249053)\) | \(7725.541\text{ms}(6442156043)\) | \(1568.539\text{ms}(1432158195)\) | \(10.988\text{ms}(3458824)\) | \(6.031\text{ms}(2655978)\) |
| 131072(heapified) | \(5.782\text{ms}(2868339)\) | \(2.804\text{ms}(1859656)\) | \(5.190\text{ms}(2387422)\) | \(7.339\text{ms}(2679776)\) | \(4426.392\text{ms}(5533146484)\) | \(6000.307\text{ms}(8589869056)\) | \(13269.253\text{ms}(8589815456)\) | \(13100.395\text{ms}(7409392845)\) | \(23055.890\text{ms}(11066161928)\) | \(17.931\text{ms}(5461420)\) | \(16.588\text{ms}(1719820)\) | \(9.285\text{ms}(2349101)\) | \(18.732\text{ms}(4909604)\) | \(17.344\text{ms}(3709348)\) | \(81.382\text{ms}(10027008)\) | \(15.219\text{ms}(4442304)\) | \(13.551\text{ms}(5030179)\) | \(11.162\text{ms}(2635821)\) | \(9.463\text{ms}(2680195)\) | \(20.703\text{ms}(4326984)\) | \(10.810\text{ms}(2828109)\) | \(9.974\text{ms}(3986988)\) | \(118.331\text{ms}(81459081)\) | \(14.235\text{ms}(10276743)\) | \(6.863\text{ms}(2613954)\) | \(13.813\text{ms}(3574259)\) | \(8.018\text{ms}(2878110)\) |
| 131072(binary search tree) | \(6.711\text{ms}(4369082)\) | \(2.298\text{ms}(1413695)\) | \(0.563\text{ms}(393321)\) | \(6.128\text{ms}(3219899)\) | \(2224.023\text{ms}(2863508120)\) | \(5732.476\text{ms}(8589869056)\) | \(6763.876\text{ms}(4295032831)\) | \(8208.105\text{ms}(4742075478)\) | \(11611.279\text{ms}(5726885186)\) | \(9.105\text{ms}(5330349)\) | \(10.935\text{ms}(1245166)\) | \(9.254\text{ms}(2211925)\) | \(17.904\text{ms}(5899730)\) | \(9.703\text{ms}(2999803)\) | \(27.170\text{ms}(10027008)\) | \(12.991\text{ms}(7679313)\) | \(11.411\text{ms}(6399676)\) | \(12.783\text{ms}(7229857)\) | \(10.171\text{ms}(4615744)\) | \(22.904\text{ms}(6021819)\) | \(11.043\text{ms}(2990090)\) | \(11.369\text{ms}(2555271)\) | \(3393.205\text{ms}(2147581952)\) | \(63.217\text{ms}(56640686)\) | \(2811.634\text{ms}(2147811322)\) | \(12.607\text{ms}(4026009)\) | \(7.214\text{ms}(2624761)\) |
| 131072(sawtooth) | \(7.878\text{ms}(2666996)\) | \(4.142\text{ms}(2029278)\) | \(6.372\text{ms}(2682912)\) | \(10.945\text{ms}(2659914)\) | \(2515.499\text{ms}(3221258239)\) | \(6132.442\text{ms}(8589869056)\) | \(13642.029\text{ms}(8052752389)\) | \(7294.218\text{ms}(5100257281)\) | \(13624.257\text{ms}(6442385407)\) | \(0.031\text{ms}(30248)\) | \(12.577\text{ms}(1851392)\) | \(10.030\text{ms}(2262907)\) | \(19.549\text{ms}(5807913)\) | \(5.239\text{ms}(2241226)\) | \(33.708\text{ms}(10027008)\) | \(12.178\text{ms}(3906054)\) | \(29.687\text{ms}(20347796)\) | \(11.220\text{ms}(2948400)\) | \(11.569\text{ms}(2559308)\) | \(24.319\text{ms}(4171198)\) | \(14.139\text{ms}(2722952)\) | \(400.241\text{ms}(276795256)\) | \(388.475\text{ms}(271542722)\) | \(266.828\text{ms}(141864628)\) | \(14.324\text{ms}(6046979)\) | \(30.183\text{ms}(3588243)\) | \(20.159\text{ms}(2689539)\) |
| 131072(scrambled head) | \(15.868\text{ms}(3204338)\) | \(8.049\text{ms}(1428683)\) | \(4.491\text{ms}(705749)\) | \(7.679\text{ms}(1055890)\) | \(2203.177\text{ms}(2617369180)\) | \(6704.447\text{ms}(8589869056)\) | \(12879.586\text{ms}(8436493750)\) | \(6203.627\text{ms}(3730843824)\) | \(10539.158\text{ms}(5234607296)\) | \(21.465\text{ms}(5461420)\) | \(21.314\text{ms}(1320451)\) | \(18.348\text{ms}(2297016)\) | \(39.355\text{ms}(5580401)\) | \(45.848\text{ms}(4402738)\) | \(65.078\text{ms}(10027008)\) | \(22.658\text{ms}(5371217)\) | \(21.053\text{ms}(6563461)\) | \(192.464\text{ms}(202527178)\) | \(6.317\text{ms}(2526225)\) | \(15.128\text{ms}(4165243)\) | \(8.169\text{ms}(2755051)\) | \(5.958\text{ms}(3440467)\) | \(212.173\text{ms}(179224512)\) | \(536.947\text{ms}(482820061)\) | \(8.426\text{ms}(2603340)\) | \(25.486\text{ms}(3478135)\) | \(19.316\text{ms}(2598609)\) |
| 131072(scrambled tail) | \(13.568\text{ms}(2687471)\) | \(8.971\text{ms}(1372817)\) | \(4.204\text{ms}(591069)\) | \(4.329\text{ms}(574841)\) | \(1018.387\text{ms}(1006854755)\) | \(5956.928\text{ms}(8589869056)\) | \(16201.864\text{ms}(8589595282)\) | \(3524.616\text{ms}(1890426047)\) | \(3846.089\text{ms}(2013578439)\) | \(19.069\text{ms}(5592491)\) | \(12.053\text{ms}(1247894)\) | \(10.433\text{ms}(2280883)\) | \(15.624\text{ms}(5354295)\) | \(20.138\text{ms}(4229698)\) | \(44.632\text{ms}(10027008)\) | \(25.070\text{ms}(14267263)\) | \(16.372\text{ms}(7620162)\) | \(280.632\text{ms}(210454957)\) | \(11.733\text{ms}(2582435)\) | \(29.484\text{ms}(4165740)\) | \(21.845\text{ms}(2724798)\) | \(53.654\text{ms}(13621799)\) | \(25.764\text{ms}(6547928)\) | \(489.867\text{ms}(210777782)\) | \(6.758\text{ms}(3413581)\) | \(11.010\text{ms}(3532550)\) | \(6.554\text{ms}(2588605)\) |
| 131072(half-reversed) | \(6.334\text{ms}(4808569)\) | \(2.070\text{ms}(1132837)\) | \(0.309\text{ms}(196607)\) | \(0.500\text{ms}(262141)\) | \(1605.139\text{ms}(2147581951)\) | \(6077.700\text{ms}(8589869056)\) | \(9411.972\text{ms}(6442418176)\) | \(3733.551\text{ms}(2147647487)\) | \(8518.458\text{ms}(4295032831)\) | \(0.165\text{ms}(30248)\) | \(10.693\text{ms}(1114112)\) | \(7.639\text{ms}(2292212)\) | \(5.750\text{ms}(2352819)\) | \(3.444\text{ms}(1933606)\) | \(25.718\text{ms}(10027008)\) | \(5082.894\text{ms}(7874183165)\) | \(1580.156\text{ms}(2505594196)\) | \(1.931\text{ms}(2031633)\) | \(1.710\text{ms}(2228238)\) | \(7.864\text{ms}(3735560)\) | \(4.265\text{ms}(2674964)\) | \(5946.211\text{ms}(4295000064)\) | \(2747.047\text{ms}(2505463124)\) | \(2.627\text{ms}(1964957)\) | \(14.918\text{ms}(12958055)\) | \(8.240\text{ms}(3545780)\) | \(5.604\text{ms}(2817338)\) |
| 131072(adversary) | \(2.988\text{ms}(2195283)\) | \(2.685\text{ms}(1719146)\) | \(2.823\text{ms}(1358033)\) | \(3.824\text{ms}(1579170)\) | \(3952.256\text{ms}(5010827946)\) | \(5826.698\text{ms}(8589869056)\) | \(10065.897\text{ms}(6442418176)\) | \(14324.222\text{ms}(8589869056)\) | \(20133.672\text{ms}(10021524821)\) | \(339.841\text{ms}(357124913)\) | \(10.929\text{ms}(1572866)\) | \(5.734\text{ms}(2227444)\) | \(8.139\text{ms}(3386134)\) | \(3.219\text{ms}(1704209)\) | \(21.156\text{ms}(10027008)\) | \(4.707\text{ms}(3074298)\) | \(61.877\text{ms}(95859104)\) | \(4.789\text{ms}(2529755)\) | \(5.577\text{ms}(2391197)\) | \(13.247\text{ms}(3587200)\) | \(6.775\text{ms}(2394073)\) | \(3698.420\text{ms}(2420298931)\) | \(2696.626\text{ms}(2692729308)\) | \(4808.696\text{ms}(4832460452)\) | \(8491.709\text{ms}(8590262265)\) | \(2517.525\text{ms}(2150477603)\) | \(2072.902\text{ms}(2155288663)\) |
表格 Part.2
这部分是六个算法在 \(n=2^{20},2^{24},2^{27},2^{30}\) 下的表现。
| data size | std::sort | std::stable_sort | Timsort | PDQ-sort | Quick sort (LR, pivot=median of 3) | Quick sort (LR, pivot=median of 9) |
|---|---|---|---|---|---|---|
| 1048576(random) | \(85.544\text{ms}(25764413)\) | \(103.060\text{ms}(20774166)\) | \(108.438\text{ms}(31374864)\) | \(90.238\text{ms}(25373781)\) | \(93.810\text{ms}(24635806)\) | \(99.635\text{ms}(27087127)\) |
| 1048576(ascending) | \(16.325\text{ms}(26869799)\) | \(18.611\text{ms}(11534334)\) | \(0.739\text{ms}(1048575)\) | \(1.378\text{ms}(1048575)\) | \(15.935\text{ms}(20971537)\) | \(19.148\text{ms}(25690120)\) |
| 1048576(descending) | \(13.403\text{ms}(19005450)\) | \(20.904\text{ms}(9736780)\) | \(1.218\text{ms}(1048575)\) | \(1.898\text{ms}(1048575)\) | \(16.487\text{ms}(20971537)\) | \(20.469\text{ms}(25690120)\) |
| 1048576(pipe organ) | \(99.395\text{ms}(61847683)\) | \(22.059\text{ms}(11159844)\) | \(2.814\text{ms}(2097150)\) | \(3.237\text{ms}(2097151)\) | \(78.423\text{ms}(85948502)\) | \(82.564\text{ms}(82140638)\) |
| 1048576(final merge) | \(13.931\text{ms}(19005452)\) | \(17.996\text{ms}(11534334)\) | \(2.247\text{ms}(1572863)\) | \(2.799\text{ms}(1572864)\) | \(17.219\text{ms}(22543513)\) | \(20.888\text{ms}(25690438)\) |
| 1048576(final merge reversed) | \(95.948\text{ms}(60006043)\) | \(21.357\text{ms}(10261067)\) | \(3.341\text{ms}(2097150)\) | \(3.346\text{ms}(2097151)\) | \(75.130\text{ms}(82078852)\) | \(80.798\text{ms}(76984980)\) |
| 1048576(heapified) | \(52.009\text{ms}(27147432)\) | \(24.556\text{ms}(17237156)\) | \(37.834\text{ms}(22702493)\) | \(60.322\text{ms}(24729025)\) | \(63.836\text{ms}(25633077)\) | \(70.606\text{ms}(27641182)\) |
| 1048576(binary search tree) | \(62.869\text{ms}(43555235)\) | \(19.034\text{ms}(12882496)\) | \(4.511\text{ms}(3145830)\) | \(4.887\text{ms}(3145873)\) | \(59.528\text{ms}(46113997)\) | \(65.166\text{ms}(46705572)\) |
| 1048576(sawtooth) | \(53.244\text{ms}(25982278)\) | \(24.377\text{ms}(18986718)\) | \(38.607\text{ms}(25395232)\) | \(55.153\text{ms}(23597424)\) | \(62.239\text{ms}(23870846)\) | \(68.039\text{ms}(26566998)\) |
| 1048576(scrambled head) | \(45.103\text{ms}(25533277)\) | \(27.397\text{ms}(13202050)\) | \(14.920\text{ms}(6222022)\) | \(34.334\text{ms}(15169528)\) | \(57.381\text{ms}(23952940)\) | \(63.445\text{ms}(27835554)\) |
| 1048576(scrambled tail) | \(44.780\text{ms}(29879870)\) | \(27.204\text{ms}(12757637)\) | \(12.586\text{ms}(5304526)\) | \(12.605\text{ms}(4727505)\) | \(55.490\text{ms}(24081257)\) | \(60.615\text{ms}(28011198)\) |
| 1048576(half-reversed) | \(58.111\text{ms}(45578992)\) | \(19.683\text{ms}(10635557)\) | \(2.467\text{ms}(1572863)\) | \(2.566\text{ms}(1572865)\) | \(15.543\text{ms}(20971537)\) | \(19.094\text{ms}(25690407)\) |
| 1048576(adversary) | \(27.442\text{ms}(21455601)\) | \(22.662\text{ms}(16112489)\) | \(20.149\text{ms}(12830201)\) | \(25.282\text{ms}(12811762)\) | \(38.230\text{ms}(22499835)\) | \(46.439\text{ms}(26306208)\) |
| \(\;\) | ||||||
| 16777216(random) | \(1465.432\text{ms}(485326863)\) | \(1884.681\text{ms}(399451365)\) | \(2046.023\text{ms}(600353286)\) | \(1695.178\text{ms}(480100617)\) | \(1727.107\text{ms}(475260012)\) | \(1817.268\text{ms}(508241744)\) |
| 16777216(ascending) | \(323.197\text{ms}(530579503)\) | \(375.702\text{ms}(218103804)\) | \(12.023\text{ms}(16777215)\) | \(21.699\text{ms}(16777215)\) | \(294.843\text{ms}(402653205)\) | \(348.837\text{ms}(478150668)\) |
| 16777216(descending) | \(268.873\text{ms}(371195914)\) | \(410.945\text{ms}(189342870)\) | \(20.480\text{ms}(16777215)\) | \(30.274\text{ms}(16777215)\) | \(300.463\text{ms}(402653205)\) | \(362.026\text{ms}(478150668)\) |
| 16777216(pipe organ) | \(1874.819\text{ms}(1197515183)\) | \(409.490\text{ms}(212111944)\) | \(45.768\text{ms}(33554430)\) | \(51.692\text{ms}(33554431)\) | \(1549.656\text{ms}(1907611651)\) | \(1722.725\text{ms}(1850124949)\) |
| 16777216(final merge) | \(265.550\text{ms}(371195916)\) | \(383.265\text{ms}(218103804)\) | \(36.831\text{ms}(25165823)\) | \(45.500\text{ms}(25165824)\) | \(338.316\text{ms}(427817761)\) | \(414.966\text{ms}(478151146)\) |
| 16777216(final merge reversed) | \(2195.735\text{ms}(1164338168)\) | \(470.000\text{ms}(197731477)\) | \(55.127\text{ms}(33554430)\) | \(59.043\text{ms}(33554431)\) | \(1637.323\text{ms}(1860578129)\) | \(1711.841\text{ms}(1733782281)\) |
| 16777216(heapified) | \(1033.294\text{ms}(513357084)\) | \(528.586\text{ms}(326128528)\) | \(757.100\text{ms}(434381327)\) | \(1190.072\text{ms}(470128717)\) | \(1242.651\text{ms}(489231812)\) | \(1297.620\text{ms}(534512158)\) |
| 16777216(binary search tree) | \(1399.266\text{ms}(885032664)\) | \(435.443\text{ms}(239674506)\) | \(73.149\text{ms}(50331746)\) | \(81.548\text{ms}(50331801)\) | \(1156.235\text{ms}(924892164)\) | \(1274.082\text{ms}(923482102)\) |
| 16777216(sawtooth) | \(1065.209\text{ms}(510535357)\) | \(543.555\text{ms}(362507696)\) | \(799.774\text{ms}(490209312)\) | \(1030.278\text{ms}(430526011)\) | \(1103.712\text{ms}(459373937)\) | \(1196.169\text{ms}(497316184)\) |
| 16777216(scrambled head) | \(913.773\text{ms}(531204456)\) | \(562.915\text{ms}(248988661)\) | \(275.433\text{ms}(111864842)\) | \(585.263\text{ms}(254238183)\) | \(1051.076\text{ms}(461784179)\) | \(1159.341\text{ms}(518273372)\) |
| 16777216(scrambled tail) | \(825.772\text{ms}(481661475)\) | \(572.370\text{ms}(241872086)\) | \(260.482\text{ms}(97184786)\) | \(246.328\text{ms}(85161406)\) | \(1015.082\text{ms}(464689492)\) | \(1113.828\text{ms}(519391156)\) |
| 16777216(half-reversed) | \(1118.921\text{ms}(880421436)\) | \(410.992\text{ms}(203723337)\) | \(43.351\text{ms}(25165823)\) | \(45.654\text{ms}(25165825)\) | \(297.046\text{ms}(402653205)\) | \(362.868\text{ms}(478151111)\) |
| 16777216(adversary) | \(549.370\text{ms}(420872649)\) | \(478.255\text{ms}(308131539)\) | \(396.320\text{ms}(247223319)\) | \(477.697\text{ms}(230681902)\) | \(697.216\text{ms}(430855326)\) | \(852.033\text{ms}(490158240)\) |
| \(\;\) | ||||||
| 134217728(random) | \(12894.276\text{ms}(4381941211)\) | \(17160.903\text{ms}(3598359344)\) | \(18796.786\text{ms}(5412924820)\) | \(15190.261\text{ms}(4265058972)\) | \(15453.558\text{ms}(4315178814)\) | \(16021.368\text{ms}(4535464298)\) |
| 134217728(ascending) | \(3114.372\text{ms}(4848615477)\) | \(3449.019\text{ms}(1946157052)\) | \(96.431\text{ms}(134217727)\) | \(174.556\text{ms}(134217727)\) | \(2569.195\text{ms}(3623878680)\) | \(3089.100\text{ms}(4227858447)\) |
| 134217728(descending) | \(2933.693\text{ms}(3372220426)\) | \(4023.368\text{ms}(1716069526)\) | \(167.515\text{ms}(134217727)\) | \(247.868\text{ms}(134217727)\) | \(2805.900\text{ms}(3623878680)\) | \(3178.673\text{ms}(4227858447)\) |
| 134217728(pipe organ) | \(17537.340\text{ms}(10805740188)\) | \(3739.918\text{ms}(1898222152)\) | \(368.321\text{ms}(268435454)\) | \(413.524\text{ms}(268435455)\) | \(15342.663\text{ms}(19489649457)\) | \(16314.267\text{ms}(18391903228)\) |
| 134217728(final merge) | \(2400.353\text{ms}(3372220428)\) | \(3407.678\text{ms}(1946157052)\) | \(295.789\text{ms}(201326591)\) | \(360.401\text{ms}(201326592)\) | \(2857.689\text{ms}(3825203677)\) | \(3281.961\text{ms}(4227859066)\) |
| 134217728(final merge reversed) | \(17050.610\text{ms}(10572588205)\) | \(3735.479\text{ms}(1783178389)\) | \(404.649\text{ms}(268435454)\) | \(442.398\text{ms}(268435455)\) | \(14920.276\text{ms}(18726866376)\) | \(16643.048\text{ms}(17281313657)\) |
| 134217728(heapified) | \(8503.685\text{ms}(4770294781)\) | \(4630.135\text{ms}(2911019373)\) | \(6164.952\text{ms}(3963321684)\) | \(9974.919\text{ms}(4158819976)\) | \(10218.383\text{ms}(4462810349)\) | \(10717.051\text{ms}(4745387539)\) |
| 134217728(binary search tree) | \(12482.568\text{ms}(8193494728)\) | \(3744.110\text{ms}(2118722699)\) | \(569.322\text{ms}(402653279)\) | \(624.841\text{ms}(402653343)\) | \(9335.464\text{ms}(8612500613)\) | \(10566.227\text{ms}(8474389699)\) |
| 134217728(sawtooth) | \(8585.545\text{ms}(4647100322)\) | \(4720.663\text{ms}(3252383152)\) | \(6656.438\text{ms}(4424990752)\) | \(9067.210\text{ms}(3771953197)\) | \(8848.610\text{ms}(4183835054)\) | \(9886.117\text{ms}(4408535401)\) |
| 134217728(scrambled head) | \(9662.267\text{ms}(5091945501)\) | \(5072.784\text{ms}(2218396995)\) | \(2456.986\text{ms}(969452029)\) | \(4503.865\text{ms}(1835511041)\) | \(8925.019\text{ms}(4188538213)\) | \(10057.651\text{ms}(4579367891)\) |
| 134217728(scrambled tail) | \(7297.748\text{ms}(5013597670)\) | \(5052.304\text{ms}(2161473383)\) | \(2298.638\text{ms}(852011525)\) | \(2072.660\text{ms}(731758859)\) | \(8808.427\text{ms}(4170317088)\) | \(9332.807\text{ms}(4629346867)\) |
| 134217728(half-reversed) | \(9846.060\text{ms}(7950689103)\) | \(3389.724\text{ms}(1831113289)\) | \(329.935\text{ms}(201326591)\) | \(341.953\text{ms}(201326593)\) | \(2613.417\text{ms}(3623878680)\) | \(3095.953\text{ms}(4227859028)\) |
| 134217728(adversary) | \(4805.027\text{ms}(3801719816)\) | \(4233.920\text{ms}(2767042258)\) | \(3592.735\text{ms}(2229444871)\) | \(4234.680\text{ms}(1998235491)\) | \(5918.804\text{ms}(3877742757)\) | \(7202.845\text{ms}(4339981732)\) |
| \(\;\) | ||||||
| 1073741824(random) | \(115873.350\text{ms}(39830061961)\) | \(161708.768\text{ms}(32008250942)\) | \(204174.519\text{ms}(48069904461)\) | \(134600.543\text{ms}(37625199042)\) | \(152252.444\text{ms}(38124755864)\) | \(138779.911\text{ms}(39687035876)\) |
| 1073741824(ascending) | \(23498.437\text{ms}(43620761659)\) | \(41600.535\text{ms}(17179869180)\) | \(1183.850\text{ms}(1073741823)\) | \(943.808\text{ms}(1073741823)\) | \(28168.654\text{ms}(32212254747)\) | \(27456.294\text{ms}(37044092946)\) |
| 1073741824(descending) | \(17951.502\text{ms}(30198988810)\) | \(42178.232\text{ms}(15339168918)\) | \(2516.636\text{ms}(1073741823)\) | \(1379.120\text{ms}(1073741823)\) | \(23829.516\text{ms}(32212254747)\) | \(27681.895\text{ms}(37044092946)\) |
| 1073741824(pipe organ) | \(160774.602\text{ms}(96185509771)\) | \(43620.998\text{ms}(16796389960)\) | \(4984.969\text{ms}(2147483646)\) | \(3539.448\text{ms}(2147483647)\) | \(154752.222\text{ms}(189488789194)\) | \(152754.592\text{ms}(178815009883)\) |
| 1073741824(final merge) | \(17902.972\text{ms}(30198988812)\) | \(38181.510\text{ms}(17179869180)\) | \(3487.029\text{ms}(1610612735)\) | \(3595.160\text{ms}(1610612736)\) | \(25948.102\text{ms}(33822865525)\) | \(29216.320\text{ms}(37044093724)\) |
| 1073741824(final merge reversed) | \(159387.604\text{ms}(93930858464)\) | \(48072.444\text{ms}(15876039829)\) | \(6489.748\text{ms}(2147483646)\) | \(4146.405\text{ms}(2147483647)\) | \(197096.992\text{ms}(183726739237)\) | \(150005.059\text{ms}(170916638099)\) |
| 1073741824(heapified) | \(73777.922\text{ms}(43061076549)\) | \(53845.645\text{ms}(25704075396)\) | \(62440.255\text{ms}(35048591264)\) | \(83172.039\text{ms}(36901865319)\) | \(84764.168\text{ms}(39735613759)\) | \(93725.583\text{ms}(41869602128)\) |
| 1073741824(binary search tree) | \(105274.718\text{ms}(74826802728)\) | \(41568.542\text{ms}(18560394380)\) | \(7138.477\text{ms}(3221225564)\) | \(5804.169\text{ms}(3221225637)\) | \(93533.630\text{ms}(78785091191)\) | \(98458.636\text{ms}(76593867418)\) |
| 1073741824(sawtooth) | \(77516.514\text{ms}(39857058016)\) | \(67533.394\text{ms}(28875985472)\) | \(83053.769\text{ms}(40164655136)\) | \(83780.208\text{ms}(32443224569)\) | \(87444.374\text{ms}(37662119858)\) | \(108242.937\text{ms}(38911107080)\) |
| 1073741824(scrambled head) | \(126481.988\text{ms}(46982002816)\) | \(79660.713\text{ms}(19559172718)\) | \(31626.560\text{ms}(8365714827)\) | \(46249.108\text{ms}(19135174905)\) | \(104309.550\text{ms}(37329500834)\) | \(115435.830\text{ms}(40364229954)\) |
| 1073741824(scrambled tail) | \(84618.883\text{ms}(39069849333)\) | \(61702.387\text{ms}(19103834422)\) | \(24353.519\text{ms}(7426190739)\) | \(18950.468\text{ms}(6278324893)\) | \(100381.674\text{ms}(37912241616)\) | \(107545.026\text{ms}(40446180770)\) |
| 1073741824(half-reversed) | \(114521.822\text{ms}(70789972630)\) | \(50298.791\text{ms}(16259519049)\) | \(4907.604\text{ms}(1610612735)\) | \(4097.957\text{ms}(1610612737)\) | \(29127.162\text{ms}(32212254747)\) | \(39994.105\text{ms}(37044093683)\) |
| 1073741824(adversary) | \(59589.135\text{ms}(34441719584)\) | \(58094.268\text{ms}(24552257233)\) | \(50388.803\text{ms}(19848888132)\) | \(49680.604\text{ms}(17055174040)\) | \(74128.562\text{ms}(34485235245)\) | \(82253.047\text{ms}(38065192456)\) |
浙公网安备 33010602011771号
协议保护。