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