2402:(1) = = = = = = = = (2) = = = = // max 1 compares (size1+size2-1), 4x repeats to concat 8 arrays with size 1 and 1 === === === === (3) = = // max 7 compares, 2x repeats to concat 4 arrays with size 2 and 2 === === ===== ===== ======= ======= (4) // max 15 compares, 1x repeats to concat 2 arrays with size 4 and 4 Formula extraction: n = 256 = 2^8 (array size in format 2^k, for simplify) On = (n-1) + 2(n/2-1) + 4(n/4-1) + 8(n/8-1) + 16(n/16-1) + 32(n/32-1) + 64(n/64-1) + 128(n/128-1) On = (n-1) + (n-2) + (n-4) + (n-8) + (n-16) + (n-32) + (n-64) + (n-128) On = n+n+n+n+n+n+n+n - (1+2+4+8+16+32+64+128) | 1+2+4... = formula for geometric sequence Sn = a1 * (q^i - 1) / (n - 1), n is number of items, a1 is first item On = 8*n - 1 * (2^8 - 1) / (2 - 1) On = 8*n - (2^8 - 1) | 2^8 = n On = 8*n - (n - 1) On = (8-1)*n + 1 | 8 = ln(n)/ln(2) = ln(256)/ln(2) On = (ln(n)/ln(2) - 1) * n + 1 Example: n = 2^4 = 16, On ~= 3*n n = 2^8 = 256, On ~= 7*n n = 2^10 = 1.024, On ~= 9*n n = 2^20 = 1.048.576, On ~= 19*n
20:
2371:
2067:-leaf binary tree (in which each leaf corresponds to a permutation). The minimum average length of a binary tree with a given number of leaves is achieved by a balanced full binary tree, because any other binary tree can have its path length reduced by moving a pair of leaves to a higher position. With some careful calculations, for a balanced full binary tree with
2096:
1619:
2032:
To unearth what happens while analyzing the average case, the key is that what does 'average' refer to? Averaging over what? With some knowledge of information theory, the information-theoretic lower bound averages over the set of all permutations as a whole. But any computer algorithms (under what
1952:
The lower bound derived via information theory is phrased as 'information-theoretic lower bound'. Information-theoretic lower bound is correct but is not necessarily the strongest lower bound. And in some cases, the information-theoretic lower bound of a problem may even be far from the true lower
331:
Despite these limitations, comparison sorts offer the notable practical advantage that control over the comparison function allows sorting of many different datatypes and fine control over how the list is sorted. For example, reversing the result of the comparison function allows the list to be
153:
For comparison-based sorts the decision to execute basic operations other than comparisons is based on the outcome of comparisons. Hence in a time analysis the number of executed comparisons is used to determine upper bound estimates for the number of executed basic operations such as swaps or
2028:
comparisons are needed by an adversarial argument. The interplay between information-theoretic lower bound and the true lower bound are much like a real-valued function lower-bounding an integer function. However, this is not exactly correct when the average case is considered.
170:
328:, or the application may benefit from sorting methods where sorted data begins to appear to the user quickly (and then user's speed of reading will be the limiting factor) as opposed to sorting methods where no output is available until the whole list is sorted.
2390:
In the case that multiple items may have the same key, there is no obvious statistical interpretation for the term "average case", so an argument like the above cannot be applied without making specific assumptions about the distribution of keys.
2366:{\displaystyle {\frac {(2n!-2^{\lfloor \log _{2}n!\rfloor +1})\cdot \lceil \log _{2}n!\rceil +(2^{\lfloor \log _{2}n!\rfloor +1}-n!)\cdot \lfloor \log _{2}n!\rfloor }{n!}}=\lceil \log _{2}n!\rceil +1-{\frac {2^{\lceil \log _{2}n!\rceil }}{n!}}}
1449:
281:
time. This is a consequence of the limited information available through comparisons alone — or, to put it differently, of the vague algebraic structure of totally ordered sets. In this sense, mergesort, heapsort, and introsort are
2808:
Stober, F., & Weiß, A. (2023). Lower Bounds for
Sorting 16, 17, and 18 Elements. In 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) (pp. 201-213). Society for Industrial and Applied
1188:
permutations exactly one of which is the list in sorted order. The sort algorithm must gain enough information from the comparisons to identify the correct permutation. If the algorithm always completes after at most
1698:. An upper bound of the same form, with the same leading term as the bound obtained from Stirling's approximation, follows from the existence of the algorithms that attain this bound in the worst case, like
161:. Their goal is to line up the weights in order by their weight without any information except that obtained by placing two weights on the scale and seeing which one is heavier (or if they weigh the same).
137:
can be swapped or otherwise re-arranged by the algorithm only when the order between these elements has been established based on the outcomes of prior comparisons. This is the case when the order between
1817:
1759:
1021:
838:
525:
2000:
1689:
1096:
896:
379:
This flexibility, together with the efficiency of the above comparison sorting algorithms on modern computers, has led to widespread preference for comparison sorts in most practical work.
376:. Additionally, once a comparison function is written, any comparison sort can be used without modification; non-comparison sorts typically require specialized versions for each datatype.
2033:
are believed currently) must treat each permutation as an individual instance of the problem. Hence, the average lower bound we're searching for is averaged over all individual cases.
1360:
286:
in terms of the number of comparisons they must perform, although this metric neglects other operations. Non-comparison sorts (such as the examples discussed below) can achieve
1441:
1300:
1614:{\displaystyle \log _{2}(n!)\geq \log _{2}\left(\left({\frac {n}{2}}\right)^{\frac {n}{2}}\right)={\frac {n}{2}}{\frac {\log n}{\log 2}}-{\frac {n}{2}}=\Theta (n\log n).}
2502:
2456:
1252:
1136:
1216:
2026:
1761:
comparisons. This lower bound is fairly good (it can be approached within a linear tolerance by a simple merge sort), but it is known to be inexact. For example,
1391:
2088:
2065:
2582:
2562:
2542:
2522:
1183:
1156:
2691:
Mark Wells, Applications of a language for computing in combinatorics, Information
Processing 65 (Proceedings of the 1965 IFIP Congress), 497–498, 1966.
1832:
1025:
2416:
If a list is already close to sorted, according to some measure of sortedness, the number of comparisons required to sort it can be smaller. An
2853:
294:) performance by using operations other than comparisons, allowing them to sidestep this lower bound (assuming elements are constant-sized).
324:
Real-world measures of sorting speed may need to take into account the ability of some algorithms to optimally use relatively fast cached
1159:
2399:
Can easy compute for real algorithm sorted-list-merging (array are sorted n-blocks with size 1, merge to 1–1 to 2, merge 2–2 to 4...).
39:) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator forms a
2918:
2890:
2676:
1764:
265:
There are fundamental limits on the performance of comparison sorts. A comparison sort must have an average-case lower bound of
35:
that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a
2941:
2877:
3249:
2383:, the information-theoretic lower bound for the average case is approximately 2.58, while the average lower bound derived via
1914:
bits. Since a comparison can give only two results, the maximum amount of information it provides is 1 bit. Therefore, after
2709:
Takumi Kasai, Shusaku Sawato, Shigeki Iwata, Thirty four comparisons are required to sort 13 items, LNCS 792, 260-269, 1994.
1712:
974:
791:
478:
1956:
1933:
bits on average. To perform the sort, complete information is needed, so the remaining entropy must be 0. It follows that
2420:
takes advantage of this "presortedness" and runs more quickly on nearly-sorted inputs, often while still maintaining an
3282:
1695:
1625:
1038:
1830:, and no simple formula for the solution is known. For some of the few concrete values that have been computed, see
1044:
844:
2666:
3382:
2956:
1826:
number of comparisons needed to sort a given number of entries is a computationally hard problem even for small
3254:
23:
Sorting a set of unlabelled weights by weight using only a balance scale requires a comparison sort algorithm.
1305:
3162:
3042:
2996:
1918:
comparisons the remaining entropy of the permutation, given the results of those comparisons, is at least
283:
3323:
2911:
373:
1396:
1165:
Given a list of distinct numbers (we can assume this because this is a worst-case analysis), there are
3302:
3167:
3022:
2654:
1260:
325:
239:
229:
157:
A metaphor for thinking about comparison sorts is that someone has a set of unlabelled weights and a
36:
2751:
Peczarski, Marcin (2007). "The Ford-Johnson algorithm is still unbeaten for less than 47 elements".
3318:
3057:
2823:, Lecture Notes in Computer Science, vol. 382, London, UK: Springer-Verlag, pp. 499–509,
2384:
2044:, the lower bound to be shown is the lower bound of the average length of root-to-leaf paths of an
2041:
2037:
1254:
cases because the keys are distinct and each comparison has only two possible outcomes. Therefore,
337:
3208:
3183:
3157:
2961:
2459:
1895:
1871:
the input is a random permutation, chosen uniformly from the set of all possible permutations of
147:
3027:
2732:
Marcin
Peczarski, New results in minimum-comparison sorting, Algorithmica 40 (2), 133–145, 2004.
2469:
2423:
224:
2741:
Marcin
Peczarski, Computer assisted research of posets, PhD thesis, University of Warsaw, 2006.
1103:
The number of comparisons that a comparison sort algorithm requires increases in proportion to
2966:
2927:
2886:
2849:
2672:
2632:
1221:
1106:
438:
bound either (the square resulting from the pairing up); the best known algorithm still takes
400:
123:
32:
321:) lower bound applies only to the case in which the input list can be in any possible order.
3269:
3136:
2904:
2824:
2760:
2650:
2624:
415:
is an example algorithm that runs in linear time. Other integer sorting algorithms, such as
2036:
To search for the lower bound relating to the non-achievability of computers, we adopt the
19:
3330:
3213:
3085:
2986:
2981:
1899:
1192:
404:
99:
2005:
1368:
2991:
2819:
Levcopoulos, Christos; Petersson, Ola (1989), "Heapsort - Adapted for
Presorted Files",
2718:
Marcin
Peczarski, Sorting 13 elements requires 34 comparisons, LNCS 2461, 785–794, 2002.
2070:
2047:
423:
419:, are not asymptotically faster than comparison sorting, but can be faster in practice.
3335:
3244:
3111:
3080:
3065:
2946:
2662:
2567:
2547:
2527:
2507:
2463:
1694:
This provides the lower-bound part of the claim. A more precise bound can be given via
1168:
1141:
310:
302:
287:
266:
214:
209:
169:
40:
1819:, but the minimal number of comparisons to sort 13 elements has been proved to be 34.
3376:
3203:
2976:
2417:
2411:
412:
298:
158:
2782:
372:
Comparison sorts generally adapt more easily to complex orders such as the order of
3218:
3131:
3001:
2872:
278:
3351:
3193:
3017:
2951:
2785:[The results of S(15) and S(19) to minimum-comparison sorting problem].
219:
1709:, rather than only asymptotic lower bound on the number of comparisons, namely
3297:
3277:
3259:
3223:
3152:
3090:
3075:
3037:
2764:
2700:
Mark Wells, Elements of
Combinatorial Computing, Pergamon Press, Oxford, 1971.
2658:
2628:
1699:
416:
254:
244:
234:
199:
2828:
2636:
2612:
3292:
3228:
3198:
3188:
3126:
3121:
3116:
3095:
3047:
3032:
1848:
A similar bound applies to the average number of comparisons. Assuming that
1185:
340:
by just creating a comparison function that compares each part in sequence:
204:
194:
184:
173:
129:
Comparison sorts studied in the literature are "comparison-based". Elements
2845:
The art of computer programming, volume 3: (2nd ed.) sorting and searching
1953:
bound. For example, the information-theoretic lower bound of selection is
1879:
it is impossible to determine which order the input is in with fewer than
3361:
3356:
3070:
189:
2843:
3287:
2821:
WADS '89: Proceedings of the
Workshop on Algorithms and Data Structures
407:, where all keys are integers. When the keys form a small (compared to
249:
2544:
in the sequence, of the number of times the sequence jumps from below
176:
in action on a list of numbers. The horizontal lines are pivot values.
2896:
2781:
Cheng, Weiyi; Liu, Xiaoguang; Wang, Gang; Liu, Jing (October 2007).
16:
Type of sorting algorithm that works by comparing pairs of elements
2613:"The Art of Computer Programming, Volume 3, Sorting and Searching"
2395:
n log n maximum number of comparisons for array-size in format 2^k
346:
tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc))
333:
168:
18:
261:
Performance limits and advantages of different sorting techniques
387:
Some sorting problems admit a strictly faster solution than the
2900:
2893:. Section 5.3.1: Minimum-Comparison Sorting, pp. 180–197.
2090:
leaves, the average length of root-to-leaf paths is given by
1852:
all keys are distinct, i.e. every comparison will give either
122:; in this case either may come first in the sorted list. In a
2671:(3rd ed.). MIT Press and McGraw-Hill. pp. 191–193.
126:, the input order determines the sorted order in this case.
1836:
1029:
1812:{\displaystyle \left\lceil \log _{2}(13!)\right\rceil =33}
2040:. Let's rephrase a bit of what our objective is. In the
2787:
Journal of
Frontiers of Computer Science and Technology
309:) time on an already-sorted or nearly-sorted list. The
1754:{\displaystyle \left\lceil \log _{2}(n!)\right\rceil }
1016:{\displaystyle \left\lceil \log _{2}(n!)\right\rceil }
833:{\displaystyle \left\lceil \log _{2}(n!)\right\rceil }
520:{\displaystyle \left\lceil \log _{2}(n!)\right\rceil }
180:
Some of the most well-known comparison sorts include:
2570:
2550:
2530:
2510:
2472:
2426:
2099:
2073:
2050:
2008:
1995:{\displaystyle \left\lceil \log _{2}(n)\right\rceil }
1959:
1767:
1715:
1628:
1452:
1399:
1371:
1308:
1263:
1224:
1195:
1171:
1144:
1109:
1047:
977:
847:
794:
481:
297:
Comparison sorts may run faster on some lists; many
3344:
3311:
3268:
3237:
3176:
3145:
3104:
3056:
3010:
2934:
2848:. USA: Addison Wesley Longman Publishing Co., Inc.
2776:
2774:
2576:
2556:
2536:
2516:
2496:
2450:
2365:
2082:
2059:
2020:
1994:
1811:
1753:
1683:
1613:
1435:
1385:
1354:
1294:
1246:
1210:
1177:
1158:is the number of elements to sort. This bound is
1150:
1130:
1090:
1023:to the actual minimum number of comparisons (from
1015:
890:
832:
519:
1894:This can be most easily seen using concepts from
1844:Lower bound for the average number of comparisons
2728:
2726:
2724:
1684:{\displaystyle \log _{2}(n!)=\Omega (n\log n).}
1091:{\displaystyle n\log _{2}n-{\frac {n}{\ln 2}}}
891:{\displaystyle n\log _{2}n-{\frac {n}{\ln 2}}}
332:sorted in reverse; and one can sort a list of
2912:
2804:
2802:
2800:
462:Number of comparisons required to sort a list
8:
2348:
2326:
2307:
2285:
2268:
2246:
2220:
2198:
2184:
2162:
2145:
2123:
1041:, this lower bound is well-approximated by
277:) comparison operations, which is known as
2919:
2905:
2897:
2569:
2549:
2529:
2509:
2471:
2425:
2333:
2325:
2319:
2292:
2253:
2205:
2197:
2169:
2130:
2122:
2100:
2098:
2072:
2049:
2007:
1969:
1958:
1777:
1766:
1725:
1714:
1633:
1627:
1574:
1545:
1535:
1517:
1503:
1485:
1457:
1451:
1398:
1375:
1370:
1328:
1307:
1268:
1262:
1229:
1223:
1194:
1170:
1143:
1108:
1070:
1055:
1046:
1037:items (for the worst case). Below: Using
987:
976:
870:
855:
846:
804:
793:
491:
480:
2885:, Second Edition. Addison-Wesley, 1997.
467:
2600:
1355:{\displaystyle f(n)\geq \log _{2}(n!).}
1218:steps, it cannot distinguish more than
971:Above: A comparison of the lower bound
399:bound for comparison sorting by using
2458:worst case time bound. An example is
424:sorting pairs of numbers by their sum
150:of these prior comparison outcomes.
7:
2606:
2604:
1657:
1587:
14:
1436:{\displaystyle n!=n(n-1)\cdots 1}
2524:is the average, over all values
1902:of such a random permutation is
2942:Computational complexity theory
2878:The Art of Computer Programming
2462:, a sorting algorithm based on
1705:The above argument provides an
1295:{\displaystyle 2^{f(n)}\geq n!}
2491:
2476:
2445:
2430:
2240:
2190:
2156:
2103:
1984:
1978:
1795:
1786:
1743:
1734:
1675:
1660:
1651:
1642:
1605:
1590:
1475:
1466:
1424:
1412:
1346:
1337:
1318:
1312:
1278:
1272:
1239:
1233:
1205:
1199:
1125:
1119:
1005:
996:
822:
813:
509:
500:
1:
1033:) required to sort a list of
2611:Wilkes, M. V. (1974-11-01).
2387:is 8/3, approximately 2.67.
362:compare(leftb, rightb)
354:compare(lefta, righta)
3399:
3250:Batcher odd–even mergesort
2668:Introduction to Algorithms
2497:{\displaystyle O(n\log k)}
2451:{\displaystyle O(n\log n)}
2409:
2842:Knuth, Donald E. (1998).
2783:"最少比较排序问题中S（15）和S（19）的解决"
2765:10.1016/j.ipl.2006.09.001
2406:Sorting a pre-sorted list
106:It is possible that both
3255:Pairwise sorting network
2829:10.1007/3-540-51542-9_41
1891:comparisons on average.
1696:Stirling's approximation
1365:By looking at the first
1247:{\displaystyle 2^{f(n)}}
1131:{\displaystyle n\log(n)}
1039:Stirling's approximation
3283:Kirkpatrick–Reisch sort
2629:10.1093/comjnl/17.4.324
369:compare(leftc, rightc)
358:leftb ≠ rightb
350:lefta ≠ righta
146:can be derived via the
3163:Oscillating merge sort
3043:Proportion extend sort
2997:Transdichotomous model
2578:
2558:
2538:
2518:
2498:
2452:
2367:
2084:
2061:
2022:
1996:
1813:
1755:
1685:
1615:
1437:
1387:
1356:
1296:
1248:
1212:
1179:
1152:
1132:
1092:
1017:
892:
834:
521:
426:is not subject to the
374:floating-point numbers
284:asymptotically optimal
177:
24:
3324:Pre-topological order
2883:Sorting and Searching
2655:Leiserson, Charles E.
2579:
2559:
2539:
2519:
2499:
2453:
2368:
2085:
2062:
2023:
1997:
1814:
1756:
1686:
1616:
1438:
1388:
1357:
1297:
1249:
1213:
1180:
1153:
1133:
1093:
1018:
893:
835:
522:
172:
43:over the data, with:
22:
3303:Merge-insertion sort
3168:Polyphase merge sort
3023:Cocktail shaker sort
2617:The Computer Journal
2568:
2548:
2528:
2508:
2470:
2424:
2097:
2071:
2048:
2006:
1957:
1765:
1713:
1626:
1450:
1397:
1369:
1306:
1261:
1222:
1211:{\displaystyle f(n)}
1193:
1169:
1160:asymptotically tight
1142:
1107:
1045:
975:
845:
792:
479:
401:non-comparison sorts
240:Merge-insertion sort
230:Cocktail shaker sort
37:three-way comparison
3319:Topological sorting
3081:Cartesian tree sort
2385:Decision tree model
2042:Decision tree model
2038:Decision tree model
2021:{\displaystyle n-1}
1386:{\displaystyle n/2}
338:lexicographic order
3209:Interpolation sort
3184:American flag sort
3177:Distribution sorts
3158:Cascade merge sort
2928:Sorting algorithms
2753:Inf. Process. Lett
2574:
2554:
2534:
2514:
2494:
2460:adaptive heap sort
2448:
2363:
2083:{\displaystyle n!}
2080:
2060:{\displaystyle n!}
2057:
2018:
1992:
1896:information theory
1809:
1751:
1681:
1611:
1433:
1383:
1352:
1302:, or equivalently
1292:
1244:
1208:
1175:
1148:
1128:
1088:
1013:
888:
830:
517:
178:
148:transitive closure
25:
3370:
3369:
3345:Impractical sorts
2855:978-0-201-89685-5
2659:Rivest, Ronald L.
2651:Cormen, Thomas H.
2577:{\displaystyle x}
2557:{\displaystyle x}
2537:{\displaystyle x}
2517:{\displaystyle k}
2376:For example, for
2361:
2280:
1937:must be at least
1582:
1569:
1543:
1525:
1511:
1178:{\displaystyle n}
1151:{\displaystyle n}
1086:
969:
968:
886:
154:assignments.
33:sorting algorithm
3390:
3383:Comparison sorts
3278:Block merge sort
3238:Concurrent sorts
3137:Patience sorting
2921:
2914:
2907:
2898:
2860:
2859:
2839:
2833:
2831:
2816:
2810:
2806:
2795:
2794:
2778:
2769:
2768:
2748:
2742:
2739:
2733:
2730:
2719:
2716:
2710:
2707:
2701:
2698:
2692:
2689:
2683:
2682:
2647:
2641:
2640:
2608:
2583:
2581:
2580:
2575:
2563:
2561:
2560:
2555:
2543:
2541:
2540:
2535:
2523:
2521:
2520:
2515:
2503:
2501:
2500:
2495:
2466:. It takes time
2457:
2455:
2454:
2449:
2382:
2372:
2370:
2369:
2364:
2362:
2360:
2352:
2351:
2338:
2337:
2320:
2297:
2296:
2281:
2279:
2271:
2258:
2257:
2230:
2229:
2210:
2209:
2174:
2173:
2155:
2154:
2135:
2134:
2101:
2089:
2087:
2086:
2081:
2066:
2064:
2063:
2058:
2027:
2025:
2024:
2019:
2001:
1999:
1998:
1993:
1991:
1987:
1974:
1973:
1948:
1932:
1913:
1890:
1839:
1822:Determining the
1818:
1816:
1815:
1810:
1802:
1798:
1782:
1781:
1760:
1758:
1757:
1752:
1750:
1746:
1730:
1729:
1690:
1688:
1687:
1682:
1638:
1637:
1620:
1618:
1617:
1612:
1583:
1575:
1570:
1568:
1557:
1546:
1544:
1536:
1531:
1527:
1526:
1518:
1516:
1512:
1504:
1490:
1489:
1462:
1461:
1442:
1440:
1439:
1434:
1392:
1390:
1389:
1384:
1379:
1361:
1359:
1358:
1353:
1333:
1332:
1301:
1299:
1298:
1293:
1282:
1281:
1253:
1251:
1250:
1245:
1243:
1242:
1217:
1215:
1214:
1209:
1184:
1182:
1181:
1176:
1157:
1155:
1154:
1149:
1137:
1135:
1134:
1129:
1097:
1095:
1094:
1089:
1087:
1085:
1071:
1060:
1059:
1032:
1022:
1020:
1019:
1014:
1012:
1008:
992:
991:
959:
897:
895:
894:
889:
887:
885:
871:
860:
859:
839:
837:
836:
831:
829:
825:
809:
808:
526:
524:
523:
518:
516:
512:
496:
495:
468:
457:
449:
437:
410:
403:; an example is
398:
3398:
3397:
3393:
3392:
3391:
3389:
3388:
3387:
3373:
3372:
3371:
3366:
3340:
3331:Pancake sorting
3307:
3264:
3233:
3214:Pigeonhole sort
3172:
3141:
3105:Insertion sorts
3100:
3086:Tournament sort
3058:Selection sorts
3052:
3006:
2987:Integer sorting
2982:Sorting network
2972:Comparison sort
2930:
2925:
2869:
2864:
2863:
2856:
2841:
2840:
2836:
2818:
2817:
2813:
2807:
2798:
2780:
2779:
2772:
2750:
2749:
2745:
2740:
2736:
2731:
2722:
2717:
2713:
2708:
2704:
2699:
2695:
2690:
2686:
2679:
2663:Stein, Clifford
2649:
2648:
2644:
2610:
2609:
2602:
2597:
2590:
2584:or vice versa.
2566:
2565:
2546:
2545:
2526:
2525:
2506:
2505:
2468:
2467:
2464:Cartesian trees
2422:
2421:
2414:
2408:
2403:
2397:
2377:
2353:
2329:
2321:
2288:
2272:
2249:
2201:
2193:
2165:
2126:
2118:
2102:
2095:
2094:
2069:
2068:
2046:
2045:
2004:
2003:
1965:
1964:
1960:
1955:
1954:
1942:
1938:
1928:!) −
1923:
1919:
1907:
1903:
1900:Shannon entropy
1884:
1880:
1846:
1831:
1773:
1772:
1768:
1763:
1762:
1721:
1720:
1716:
1711:
1710:
1629:
1624:
1623:
1558:
1547:
1499:
1498:
1494:
1481:
1453:
1448:
1447:
1395:
1394:
1367:
1366:
1324:
1304:
1303:
1264:
1259:
1258:
1225:
1220:
1219:
1191:
1190:
1167:
1166:
1140:
1139:
1105:
1104:
1101:
1100:
1099:
1075:
1051:
1043:
1042:
1024:
983:
982:
978:
973:
972:
957:
875:
851:
843:
842:
800:
799:
795:
790:
789:
487:
486:
482:
477:
476:
464:
451:
450:time, but only
439:
427:
422:The problem of
408:
405:integer sorting
388:
385:
370:
326:computer memory
263:
167:
29:comparison sort
17:
12:
11:
5:
3396:
3394:
3386:
3385:
3375:
3374:
3368:
3367:
3365:
3364:
3359:
3354:
3348:
3346:
3342:
3341:
3339:
3338:
3336:Spaghetti sort
3333:
3328:
3327:
3326:
3315:
3313:
3309:
3308:
3306:
3305:
3300:
3295:
3290:
3285:
3280:
3274:
3272:
3266:
3265:
3263:
3262:
3257:
3252:
3247:
3245:Bitonic sorter
3241:
3239:
3235:
3234:
3232:
3231:
3226:
3221:
3216:
3211:
3206:
3201:
3196:
3191:
3186:
3180:
3178:
3174:
3173:
3171:
3170:
3165:
3160:
3155:
3149:
3147:
3143:
3142:
3140:
3139:
3134:
3129:
3124:
3119:
3114:
3112:Insertion sort
3108:
3106:
3102:
3101:
3099:
3098:
3096:Weak-heap sort
3093:
3088:
3083:
3078:
3073:
3068:
3066:Selection sort
3062:
3060:
3054:
3053:
3051:
3050:
3045:
3040:
3035:
3030:
3025:
3020:
3014:
3012:
3011:Exchange sorts
3008:
3007:
3005:
3004:
2999:
2994:
2989:
2984:
2979:
2974:
2969:
2964:
2959:
2954:
2949:
2947:Big O notation
2944:
2938:
2936:
2932:
2931:
2926:
2924:
2923:
2916:
2909:
2901:
2895:
2894:
2868:
2865:
2862:
2861:
2854:
2834:
2811:
2796:
2789:(in Chinese).
2770:
2759:(3): 126–128.
2743:
2734:
2720:
2711:
2702:
2693:
2684:
2677:
2642:
2623:(4): 324–324.
2599:
2598:
2596:
2593:
2589:
2586:
2573:
2553:
2533:
2513:
2493:
2490:
2487:
2484:
2481:
2478:
2475:
2447:
2444:
2441:
2438:
2435:
2432:
2429:
2410:Main article:
2407:
2404:
2401:
2396:
2393:
2381: = 3
2374:
2373:
2359:
2356:
2350:
2347:
2344:
2341:
2336:
2332:
2328:
2324:
2318:
2315:
2312:
2309:
2306:
2303:
2300:
2295:
2291:
2287:
2284:
2278:
2275:
2270:
2267:
2264:
2261:
2256:
2252:
2248:
2245:
2242:
2239:
2236:
2233:
2228:
2225:
2222:
2219:
2216:
2213:
2208:
2204:
2200:
2196:
2192:
2189:
2186:
2183:
2180:
2177:
2172:
2168:
2164:
2161:
2158:
2153:
2150:
2147:
2144:
2141:
2138:
2133:
2129:
2125:
2121:
2117:
2114:
2111:
2108:
2105:
2079:
2076:
2056:
2053:
2017:
2014:
2011:
1990:
1986:
1983:
1980:
1977:
1972:
1968:
1963:
1940:
1921:
1905:
1882:
1877:
1876:
1869:
1845:
1842:
1808:
1805:
1801:
1797:
1794:
1791:
1788:
1785:
1780:
1776:
1771:
1749:
1745:
1742:
1739:
1736:
1733:
1728:
1724:
1719:
1692:
1691:
1680:
1677:
1674:
1671:
1668:
1665:
1662:
1659:
1656:
1653:
1650:
1647:
1644:
1641:
1636:
1632:
1621:
1610:
1607:
1604:
1601:
1598:
1595:
1592:
1589:
1586:
1581:
1578:
1573:
1567:
1564:
1561:
1556:
1553:
1550:
1542:
1539:
1534:
1530:
1524:
1521:
1515:
1510:
1507:
1502:
1497:
1493:
1488:
1484:
1480:
1477:
1474:
1471:
1468:
1465:
1460:
1456:
1432:
1429:
1426:
1423:
1420:
1417:
1414:
1411:
1408:
1405:
1402:
1382:
1378:
1374:
1363:
1362:
1351:
1348:
1345:
1342:
1339:
1336:
1331:
1327:
1323:
1320:
1317:
1314:
1311:
1291:
1288:
1285:
1280:
1277:
1274:
1271:
1267:
1241:
1238:
1235:
1232:
1228:
1207:
1204:
1201:
1198:
1174:
1147:
1127:
1124:
1121:
1118:
1115:
1112:
1084:
1081:
1078:
1074:
1069:
1066:
1063:
1058:
1054:
1050:
1011:
1007:
1004:
1001:
998:
995:
990:
986:
981:
970:
967:
966:
963:
960:
954:
953:
950:
947:
943:
942:
939:
936:
932:
931:
928:
925:
921:
920:
917:
914:
910:
909:
906:
903:
899:
898:
884:
881:
878:
874:
869:
866:
863:
858:
854:
850:
840:
828:
824:
821:
818:
815:
812:
807:
803:
798:
787:
781:
780:
778:
776:
773:
772:
769:
766:
762:
761:
758:
755:
751:
750:
747:
744:
740:
739:
736:
733:
729:
728:
725:
722:
718:
717:
714:
711:
707:
706:
703:
700:
696:
695:
692:
689:
685:
684:
681:
678:
674:
673:
670:
667:
663:
662:
659:
656:
652:
651:
648:
645:
641:
640:
637:
634:
630:
629:
626:
623:
619:
618:
615:
612:
608:
607:
604:
601:
597:
596:
593:
590:
586:
585:
582:
579:
575:
574:
571:
568:
564:
563:
560:
557:
553:
552:
549:
546:
542:
541:
538:
535:
531:
530:
527:
515:
511:
508:
505:
502:
499:
494:
490:
485:
474:
466:
465:
463:
460:
384:
381:
342:
303:insertion sort
299:adaptive sorts
262:
259:
258:
257:
252:
247:
242:
237:
232:
227:
222:
217:
215:Selection sort
212:
210:Insertion sort
207:
202:
197:
192:
187:
166:
163:
104:
103:
72:
71:(transitivity)
41:total preorder
15:
13:
10:
9:
6:
4:
3:
2:
3395:
3384:
3381:
3380:
3378:
3363:
3360:
3358:
3355:
3353:
3350:
3349:
3347:
3343:
3337:
3334:
3332:
3329:
3325:
3322:
3321:
3320:
3317:
3316:
3314:
3310:
3304:
3301:
3299:
3296:
3294:
3291:
3289:
3286:
3284:
3281:
3279:
3276:
3275:
3273:
3271:
3267:
3261:
3258:
3256:
3253:
3251:
3248:
3246:
3243:
3242:
3240:
3236:
3230:
3227:
3225:
3222:
3220:
3217:
3215:
3212:
3210:
3207:
3205:
3204:Counting sort
3202:
3200:
3197:
3195:
3192:
3190:
3187:
3185:
3182:
3181:
3179:
3175:
3169:
3166:
3164:
3161:
3159:
3156:
3154:
3151:
3150:
3148:
3144:
3138:
3135:
3133:
3130:
3128:
3125:
3123:
3120:
3118:
3115:
3113:
3110:
3109:
3107:
3103:
3097:
3094:
3092:
3089:
3087:
3084:
3082:
3079:
3077:
3074:
3072:
3069:
3067:
3064:
3063:
3061:
3059:
3055:
3049:
3046:
3044:
3041:
3039:
3036:
3034:
3031:
3029:
3028:Odd–even sort
3026:
3024:
3021:
3019:
3016:
3015:
3013:
3009:
3003:
3000:
2998:
2995:
2993:
2992:X + Y sorting
2990:
2988:
2985:
2983:
2980:
2978:
2977:Adaptive sort
2975:
2973:
2970:
2968:
2965:
2963:
2960:
2958:
2955:
2953:
2950:
2948:
2945:
2943:
2940:
2939:
2937:
2933:
2929:
2922:
2917:
2915:
2910:
2908:
2903:
2902:
2899:
2892:
2891:0-201-89685-0
2888:
2884:
2880:
2879:
2874:
2871:
2870:
2866:
2857:
2851:
2847:
2846:
2838:
2835:
2830:
2826:
2822:
2815:
2812:
2805:
2803:
2801:
2797:
2793:(3): 305–313.
2792:
2788:
2784:
2777:
2775:
2771:
2766:
2762:
2758:
2754:
2747:
2744:
2738:
2735:
2729:
2727:
2725:
2721:
2715:
2712:
2706:
2703:
2697:
2694:
2688:
2685:
2680:
2678:0-262-03384-4
2674:
2670:
2669:
2664:
2660:
2656:
2652:
2646:
2643:
2638:
2634:
2630:
2626:
2622:
2618:
2614:
2607:
2605:
2601:
2594:
2592:
2587:
2585:
2571:
2551:
2531:
2511:
2488:
2485:
2482:
2479:
2473:
2465:
2461:
2442:
2439:
2436:
2433:
2427:
2419:
2418:adaptive sort
2413:
2412:Adaptive sort
2405:
2400:
2394:
2392:
2388:
2386:
2380:
2357:
2354:
2345:
2342:
2339:
2334:
2330:
2322:
2316:
2313:
2310:
2304:
2301:
2298:
2293:
2289:
2282:
2276:
2273:
2265:
2262:
2259:
2254:
2250:
2243:
2237:
2234:
2231:
2226:
2223:
2217:
2214:
2211:
2206:
2202:
2194:
2187:
2181:
2178:
2175:
2170:
2166:
2159:
2151:
2148:
2142:
2139:
2136:
2131:
2127:
2119:
2115:
2112:
2109:
2106:
2093:
2092:
2091:
2077:
2074:
2054:
2051:
2043:
2039:
2034:
2030:
2015:
2012:
2009:
1988:
1981:
1975:
1970:
1966:
1961:
1950:
1949:on average.
1946:
1936:
1931:
1927:
1917:
1911:
1901:
1897:
1892:
1888:
1874:
1870:
1867:
1863:
1859:
1855:
1851:
1850:
1849:
1843:
1841:
1838:
1834:
1829:
1825:
1820:
1806:
1803:
1799:
1792:
1789:
1783:
1778:
1774:
1769:
1747:
1740:
1737:
1731:
1726:
1722:
1717:
1708:
1703:
1701:
1697:
1678:
1672:
1669:
1666:
1663:
1654:
1648:
1645:
1639:
1634:
1630:
1622:
1608:
1602:
1599:
1596:
1593:
1584:
1579:
1576:
1571:
1565:
1562:
1559:
1554:
1551:
1548:
1540:
1537:
1532:
1528:
1522:
1519:
1513:
1508:
1505:
1500:
1495:
1491:
1486:
1482:
1478:
1472:
1469:
1463:
1458:
1454:
1446:
1445:
1444:
1430:
1427:
1421:
1418:
1415:
1409:
1406:
1403:
1400:
1380:
1376:
1372:
1349:
1343:
1340:
1334:
1329:
1325:
1321:
1315:
1309:
1289:
1286:
1283:
1275:
1269:
1265:
1257:
1256:
1255:
1236:
1230:
1226:
1202:
1196:
1187:
1172:
1163:
1161:
1145:
1122:
1116:
1113:
1110:
1082:
1079:
1076:
1072:
1067:
1064:
1061:
1056:
1052:
1048:
1040:
1036:
1031:
1027:
1009:
1002:
999:
993:
988:
984:
979:
964:
961:
956:
955:
951:
948:
945:
944:
940:
937:
934:
933:
929:
926:
923:
922:
918:
915:
912:
911:
907:
904:
901:
900:
882:
879:
876:
872:
867:
864:
861:
856:
852:
848:
841:
826:
819:
816:
810:
805:
801:
796:
788:
786:
783:
782:
779:
777:
775:
774:
770:
767:
764:
763:
759:
756:
753:
752:
748:
745:
742:
741:
737:
734:
731:
730:
726:
723:
720:
719:
715:
712:
709:
708:
704:
701:
698:
697:
693:
690:
687:
686:
682:
679:
676:
675:
671:
668:
665:
664:
660:
657:
654:
653:
649:
646:
643:
642:
638:
635:
632:
631:
627:
624:
621:
620:
616:
613:
610:
609:
605:
602:
599:
598:
594:
591:
588:
587:
583:
580:
577:
576:
572:
569:
566:
565:
561:
558:
555:
554:
550:
547:
544:
543:
539:
536:
533:
532:
528:
513:
506:
503:
497:
492:
488:
483:
475:
473:
470:
469:
461:
459:
458:comparisons.
455:
447:
443:
435:
431:
425:
420:
418:
414:
413:counting sort
406:
402:
396:
392:
382:
380:
377:
375:
368:
365:
361:
357:
353:
349:
345:
341:
339:
335:
329:
327:
322:
320:
316:
312:
308:
304:
300:
295:
293:
289:
285:
280:
276:
272:
268:
260:
256:
253:
251:
248:
246:
243:
241:
238:
236:
233:
231:
228:
226:
225:Odd–even sort
223:
221:
218:
216:
213:
211:
208:
206:
203:
201:
198:
196:
193:
191:
188:
186:
183:
182:
181:
175:
171:
164:
162:
160:
159:balance scale
155:
151:
149:
145:
141:
136:
132:
127:
125:
121:
117:
113:
109:
101:
97:
93:
89:
85:
81:
77:
73:
70:
66:
62:
58:
54:
50:
46:
45:
44:
42:
38:
34:
31:is a type of
30:
21:
3270:Hybrid sorts
3219:Proxmap sort
3132:Library sort
3002:Quantum sort
2971:
2882:
2881:, Volume 3:
2876:
2873:Donald Knuth
2844:
2837:
2820:
2814:
2790:
2786:
2756:
2752:
2746:
2737:
2714:
2705:
2696:
2687:
2667:
2645:
2620:
2616:
2591:
2415:
2398:
2389:
2378:
2375:
2035:
2031:
1951:
1944:
1934:
1929:
1925:
1915:
1909:
1893:
1886:
1878:
1872:
1865:
1861:
1857:
1853:
1847:
1827:
1823:
1821:
1706:
1704:
1693:
1443:, we obtain
1364:
1164:
1102:
1034:
784:
471:
453:
445:
441:
433:
429:
421:
394:
390:
386:
383:Alternatives
378:
371:
366:
363:
359:
355:
351:
347:
343:
330:
323:
318:
314:
306:
296:
291:
279:linearithmic
274:
270:
264:
179:
156:
152:
143:
139:
134:
130:
128:
119:
115:
111:
107:
105:
95:
91:
87:
83:
79:
75:
68:
64:
60:
56:
52:
48:
28:
26:
3352:Stooge sort
3194:Bucket sort
3146:Merge sorts
3018:Bubble sort
2962:Inplacement
2952:Total order
2809:Mathematics
1393:factors of
965:18 488 874
962:18 488 885
220:Bubble sort
124:stable sort
3298:Spreadsort
3260:Samplesort
3224:Radix sort
3153:Merge sort
3091:Cycle sort
3076:Smoothsort
3038:Gnome sort
2867:References
1700:merge sort
952:1 516 695
949:1 516 705
417:radix sort
255:Block sort
245:Smoothsort
235:Cycle sort
200:Merge sort
3293:Introsort
3229:Flashsort
3199:Burstsort
3189:Bead sort
3127:Tree sort
3122:Splaysort
3117:Shellsort
3048:Quicksort
3033:Comb sort
2967:Stability
2665:(2009) .
2637:0010-4620
2564:to above
2486:
2440:
2349:⌉
2340:
2327:⌈
2317:−
2308:⌉
2299:
2286:⌈
2269:⌋
2260:
2247:⌊
2244:⋅
2232:−
2221:⌋
2212:
2199:⌊
2185:⌉
2176:
2163:⌈
2160:⋅
2146:⌋
2137:
2124:⌊
2116:−
2013:−
1976:
1875:elements,
1784:
1732:
1670:
1658:Ω
1640:
1600:
1588:Θ
1572:−
1563:
1552:
1492:
1479:≥
1464:
1428:⋯
1419:−
1335:
1322:≥
1284:≥
1186:factorial
1117:
1080:
1068:−
1062:
994:
958:1 000 000
880:
868:−
862:
811:
498:
411:) range,
305:run in O(
205:Introsort
195:Shellsort
185:Quicksort
174:Quicksort
100:connexity
3377:Category
3362:Bogosort
3357:Slowsort
3071:Heapsort
2504:, where
2002:whereas
1989:⌉
1962:⌈
1800:⌉
1770:⌈
1748:⌉
1718:⌈
1707:absolute
1138:, where
1010:⌉
980:⌈
946:100 000
941:118 451
938:118 459
827:⌉
797:⌈
529:Minimum
514:⌉
484:⌈
344:function
301:such as
190:Heapsort
165:Examples
74:for all
3288:Timsort
1837:A036604
1835::
1030:A036604
1028::
935:10 000
356:else if
250:Timsort
2935:Theory
2889:
2852:
2675:
2635:
1898:. The
930:8 524
927:8 530
924:1 000
444:² log
432:² log
367:return
360:return
352:return
334:tuples
3312:Other
2957:Lists
2595:Notes
2588:Notes
1868:, and
1824:exact
63:then
2887:ISBN
2850:ISBN
2673:ISBN
2633:ISSN
1864:<
1856:>
1833:OEIS
1026:OEIS
919:521
916:525
913:100
393:log
364:else
317:log
273:log
142:and
133:and
114:and
78:and
55:and
2825:doi
2761:doi
2757:101
2625:doi
2483:log
2437:log
2331:log
2290:log
2251:log
2203:log
2167:log
2128:log
1967:log
1939:log
1920:log
1904:log
1881:log
1860:or
1775:log
1723:log
1667:log
1631:log
1597:log
1560:log
1549:log
1483:log
1455:log
1326:log
1114:log
1053:log
985:log
908:19
905:22
902:10
853:log
802:log
771:71
768:70
765:22
760:66
757:66
754:21
749:62
746:62
743:20
738:58
735:57
732:19
727:54
724:53
721:18
716:50
713:49
710:17
705:46
702:45
699:16
694:42
691:41
688:15
683:38
680:37
677:14
672:34
669:33
666:13
661:30
658:29
655:12
650:26
647:26
644:11
639:22
636:22
633:10
628:19
625:19
617:16
614:16
606:13
603:13
595:10
592:10
489:log
336:in
90:or
47:if
3379::
2875:.
2799:^
2773:^
2755:.
2723:^
2661:;
2657:;
2653:;
2631:.
2621:17
2619:.
2615:.
2603:^
1947:!)
1912:!)
1889:!)
1840:.
1807:33
1790:13
1702:.
1162:.
1077:ln
877:ln
622:9
611:8
600:7
589:6
584:7
581:7
578:5
573:5
570:5
567:4
562:3
559:3
556:3
551:1
548:1
545:2
540:0
537:0
534:1
456:²)
452:O(
440:O(
428:Ω(
389:Ω(
348:if
118:≤
110:≤
102:).
94:≤
86:≤
82:,
67:≤
59:≤
51:≤
27:A
2920:e
2913:t
2906:v
2858:.
2832:.
2827::
2791:1
2767:.
2763::
2681:.
2639:.
2627::
2572:x
2552:x
2532:x
2512:k
2492:)
2489:k
2480:n
2477:(
2474:O
2446:)
2443:n
2434:n
2431:(
2428:O
2379:n
2358:!
2355:n
2346:!
2343:n
2335:2
2323:2
2314:1
2311:+
2305:!
2302:n
2294:2
2283:=
2277:!
2274:n
2266:!
2263:n
2255:2
2241:)
2238:!
2235:n
2227:1
2224:+
2218:!
2215:n
2207:2
2195:2
2191:(
2188:+
2182:!
2179:n
2171:2
2157:)
2152:1
2149:+
2143:!
2140:n
2132:2
2120:2
2113:!
2110:n
2107:2
2104:(
2078:!
2075:n
2055:!
2052:n
2016:1
2010:n
1985:)
1982:n
1979:(
1971:2
1945:n
1943:(
1941:2
1935:k
1930:k
1926:n
1924:(
1922:2
1916:k
1910:n
1908:(
1906:2
1887:n
1885:(
1883:2
1873:n
1866:b
1862:a
1858:b
1854:a
1828:n
1804:=
1796:)
1793:!
1787:(
1779:2
1744:)
1741:!
1738:n
1735:(
1727:2
1679:.
1676:)
1673:n
1664:n
1661:(
1655:=
1652:)
1649:!
1646:n
1643:(
1635:2
1609:.
1606:)
1603:n
1594:n
1591:(
1585:=
1580:2
1577:n
1566:2
1555:n
1541:2
1538:n
1533:=
1529:)
1523:2
1520:n
1514:)
1509:2
1506:n
1501:(
1496:(
1487:2
1476:)
1473:!
1470:n
1467:(
1459:2
1431:1
1425:)
1422:1
1416:n
1413:(
1410:n
1407:=
1404:!
1401:n
1381:2
1377:/
1373:n
1350:.
1347:)
1344:!
1341:n
1338:(
1330:2
1319:)
1316:n
1313:(
1310:f
1290:!
1287:n
1279:)
1276:n
1273:(
1270:f
1266:2
1240:)
1237:n
1234:(
1231:f
1227:2
1206:)
1203:n
1200:(
1197:f
1173:n
1146:n
1126:)
1123:n
1120:(
1111:n
1098:.
1083:2
1073:n
1065:n
1057:2
1049:n
1035:n
1006:)
1003:!
1000:n
997:(
989:2
883:2
873:n
865:n
857:2
849:n
823:)
820:!
817:n
814:(
806:2
785:n
510:)
507:!
504:n
501:(
493:2
472:n
454:n
448:)
446:n
442:n
436:)
434:n
430:n
409:n
397:)
395:n
391:n
319:n
315:n
313:(
311:Ω
307:n
292:n
290:(
288:O
275:n
271:n
269:(
267:Ω
144:b
140:a
135:b
131:a
120:a
116:b
112:b
108:a
98:(
96:a
92:b
88:b
84:a
80:b
76:a
69:c
65:a
61:c
57:b
53:b
49:a
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
