600:
The current algorithm is based on pattern-defeating quicksort by Orson Peters, which combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on slices with certain patterns. It uses some randomization to avoid degenerate cases, but with
276:
In quicksort, one of the critical operations is choosing the pivot: the element around which the list is partitioned. The simplest pivot selection algorithm is to take the first or the last element of the list as the pivot, causing poor behavior for the case of sorted or nearly sorted input.
409:, starting from version 14 (2020), uses a hybrid sorting algorithm that uses merge sort for highly structured arrays (arrays that are composed of a small number of sorted subarrays) and introsort otherwise to sort arrays of ints, longs, floats and doubles.
378:
is different for different data types (30 if swaps are trivial, 6 otherwise). Also, arrays with sizes up to 5 are handled separately. Kutenin (2022) provides an overview for some changes made by LLVM, with a focus on the 2022 fix for quadraticness.
285:) for contrived sequences. The median-of-3 pivot selection algorithm takes the median of the first, middle, and last elements of the list; however, even though this performs well on many real-world inputs, it is still possible to contrive a
342:
uses the Musser introsort approach with the recursion depth to switch to heapsort passed as a parameter, median-of-3 pivot selection and the Knuth final insertion sort pass for partitions smaller than 16.
126:
when the number of elements is below some threshold. This combines the good parts of the three algorithms, with practical performance comparable to quicksort on typical data sets and worst-case
292:
Musser reported that on a median-of-3 killer sequence of 100,000 elements, introsort's running time was 1/200 that of median-of-3 quicksort. Musser also considered the effect on
308:
was significantly better and should be retained for template libraries, in part because the gain in other cases from doing the sorts immediately was not great.
498:
177:
which had both fast average performance and optimal worst-case performance, thus allowing the performance requirements to be tightened. Introsort is
550:
663:
169:
and thus provides worst-case linear complexity, which is optimal. Both algorithms were introduced with the purpose of providing
511:
297:
647:
403:
and more advanced median of three medians for pivot selection. Prior to version 1.19 it used shell sort for small slices.
712:
683:
735:
487:
110:
that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with
1043:
448:
66:
45:
591:
422:
Pattern-defeating quicksort (pdqsort) is a variant of introsort incorporating the following improvements:
1076:
444:
406:
539:
347:
874:
1176:
750:
392:
332:
1048:
383:
528:
452:
956:
836:
790:
760:
289:
list that will cause dramatic slowdown of a quicksort based on this pivot selection technique.
182:
174:
1117:
705:
304:. He reported that it could double the number of cache misses, but that its performance with
1096:
961:
816:
230:
The factor 2 in the maximum depth is arbitrary; it can be tuned for practical performance.
38:
8:
1112:
851:
158:
1002:
977:
951:
755:
571:
386:
305:
300:'s delayed small sorting, where small ranges are sorted at the end in a single pass of
178:
821:
721:
679:
193:
If a heapsort implementation and partitioning functions of the type discussed in the
170:
166:
107:
28:
889:
429:"BlockQuicksort" partitioning technique to mitigate branch misprediction penalities,
1063:
930:
698:
659:
618:
472:
328:
317:
281:'s variant uses the middle element to prevent these occurrences, degenerating to O(
104:
225:// assume this function does pivot selection, p is the final position of the pivot
1124:
1007:
879:
780:
775:
765:
623:
139:
69:
48:
667:
389:, starting from version 4.5 (2012), uses introsort instead of simple quicksort.
364:
1129:
1038:
905:
859:
785:
740:
396:
375:
358:
301:
127:
123:
1170:
997:
770:
433:
339:
278:
237:
395:
uses a modification of introsort: for slices of 12 or less elements it uses
1012:
925:
795:
643:
476:
321:
146:
664:
10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#
1145:
987:
811:
745:
335:
162:
154:
1091:
1071:
1053:
1017:
946:
884:
869:
831:
138:) runtime due to the heap sort. Since the three algorithms it uses are
617:. IJCAR 2020: Automated Reasoning. Vol. 12167. pp. 307–323.
1022:
992:
982:
920:
915:
910:
841:
826:
690:
439:
Use element shuffling on bad cases before trying the slower heapsort.
293:
194:
119:
111:
260:. The indices are assumed to start with 1 (the first element of the
197:
article are available, the introsort can be described succinctly as
1155:
1150:
864:
576:
115:
563:
1081:
227:
introsort(A, maxdepth - 1) introsort(A, maxdepth - 1)
122:
of) the number of elements being sorted and it switches to
615:
Efficient
Verified Implementation of Introsort and Pdqsort
350:
is similar: uses introsort with a maximum depth of 2×log
118:
when the recursion depth exceeds a level based on (the
601:
a fixed seed to always provide deterministic behavior.
432:
Linear time performance for certain input patterns (
512:"Changing std::sort at Google's Scale and Beyond"
367:also uses introsort with a maximum depth of 2×log
316:Introsort or some variant is used in a number of
1168:
648:"Introspective Sorting and Selection Algorithms"
211:introsort(A, maxdepth): n ← length(A)
165:(a variant of quicksort), which falls back to
706:
207:(length(A))⌋ × 2 introsort(A, maxdepth)
564:"orlp/pdqsort: Pattern-defeating quicksort"
503:
488:libstdc++ Documentation: Sorting Algorithms
713:
699:
622:
575:
203:sort(A : array): maxdepth ← ⌊log
215:n < 16: insertionsort(A)
612:
509:
1169:
720:
642:
561:
219:maxdepth = 0: heapsort(A)
150:
694:
592:"slice.sort_unstable(&mut self)"
13:
311:
14:
1188:
652:Software: Practice and Experience
510:Kutenin, Danila (20 April 2022).
399:, and for larger slices it uses
142:, it is also a comparison sort.
736:Computational complexity theory
606:
361:on partitions smaller than 16.
320:sort functions, including some
676:Algorithms and Data Structures
584:
555:
544:
533:
522:
492:
481:
465:
153:, in which he also introduced
1:
678:. Prentice-Hall, Inc., 1985.
458:
374:, however the size limit for
188:
624:10.1007/978-3-030-51054-1_18
562:Peters, Orson R. L. (2021).
400:
223:: p ← partition(A)
7:
412:
401:pattern-defeating quicksort
271:
10:
1193:
1044:Batcher odd–even mergesort
635:
417:
145:Introsort was invented by
1138:
1105:
1062:
1031:
970:
939:
898:
850:
804:
728:
529:Array.Sort Method (Array)
426:Median-of-three pivoting,
333:Standard Template Library
86:
65:
44:
34:
24:
1049:Pairwise sorting network
499:libc++ source code: sort
384:Microsoft .NET Framework
348:GNU Standard C++ library
16:Hybrid sorting algorithm
1077:Kirkpatrick–Reisch sort
613:Lammich, Peter (2020).
957:Oscillating merge sort
837:Proportion extend sort
791:Transdichotomous model
451:, and the C++ library
1118:Pre-topological order
540:Go 1.20.3 source code
1097:Merge-insertion sort
962:Polyphase merge sort
817:Cocktail shaker sort
175:C++ Standard Library
1113:Topological sorting
875:Cartesian tree sort
551:Java 14 source code
443:pdqsort is used by
306:double-ended queues
159:selection algorithm
21:
1003:Interpolation sort
978:American flag sort
971:Distribution sorts
952:Cascade merge sort
722:Sorting algorithms
516:Experimental chill
473:Generic Algorithms
338:implementation of
287:median-of-3 killer
171:generic algorithms
101:introspective sort
19:
1164:
1163:
1139:Impractical sorts
357:, followed by an
324:implementations.
167:median of medians
114:, it switches to
108:sorting algorithm
94:
93:
29:Sorting algorithm
1184:
1177:Comparison sorts
1072:Block merge sort
1032:Concurrent sorts
931:Patience sorting
715:
708:
701:
692:
691:
671:
670:on 7 March 2023.
666:. Archived from
644:Musser, David R.
629:
628:
626:
610:
604:
603:
588:
582:
581:
579:
559:
553:
548:
542:
537:
531:
526:
520:
519:
507:
501:
496:
490:
485:
479:
469:
318:standard library
267:
263:
259:
253:
247:
243:
235:
140:comparison sorts
22:
18:
1192:
1191:
1187:
1186:
1185:
1183:
1182:
1181:
1167:
1166:
1165:
1160:
1134:
1125:Pancake sorting
1101:
1058:
1027:
1008:Pigeonhole sort
966:
935:
899:Insertion sorts
894:
880:Tournament sort
852:Selection sorts
846:
800:
781:Integer sorting
776:Sorting network
766:Comparison sort
724:
719:
689:
674:Niklaus Wirth.
638:
633:
632:
611:
607:
590:
589:
585:
560:
556:
549:
545:
538:
534:
527:
523:
508:
504:
497:
493:
486:
482:
470:
466:
461:
420:
415:
370:
353:
314:
312:Implementations
274:
265:
261:
255:
249:
248:including both
245:
241:
231:
228:
206:
191:
17:
12:
11:
5:
1190:
1180:
1179:
1162:
1161:
1159:
1158:
1153:
1148:
1142:
1140:
1136:
1135:
1133:
1132:
1130:Spaghetti sort
1127:
1122:
1121:
1120:
1109:
1107:
1103:
1102:
1100:
1099:
1094:
1089:
1084:
1079:
1074:
1068:
1066:
1060:
1059:
1057:
1056:
1051:
1046:
1041:
1039:Bitonic sorter
1035:
1033:
1029:
1028:
1026:
1025:
1020:
1015:
1010:
1005:
1000:
995:
990:
985:
980:
974:
972:
968:
967:
965:
964:
959:
954:
949:
943:
941:
937:
936:
934:
933:
928:
923:
918:
913:
908:
906:Insertion sort
902:
900:
896:
895:
893:
892:
890:Weak-heap sort
887:
882:
877:
872:
867:
862:
860:Selection sort
856:
854:
848:
847:
845:
844:
839:
834:
829:
824:
819:
814:
808:
806:
805:Exchange sorts
802:
801:
799:
798:
793:
788:
783:
778:
773:
768:
763:
758:
753:
748:
743:
741:Big O notation
738:
732:
730:
726:
725:
718:
717:
710:
703:
695:
688:
687:
672:
658:(8): 983–993.
639:
637:
634:
631:
630:
605:
583:
554:
543:
532:
521:
502:
491:
480:
463:
462:
460:
457:
441:
440:
437:
430:
427:
419:
416:
414:
411:
397:insertion sort
376:insertion sort
368:
359:insertion sort
351:
327:The June 2000
313:
310:
302:insertion sort
273:
270:
204:
199:
190:
187:
124:insertion sort
92:
91:
88:
84:
83:
72:
63:
62:
51:
42:
41:
36:
35:Data structure
32:
31:
26:
15:
9:
6:
4:
3:
2:
1189:
1178:
1175:
1174:
1172:
1157:
1154:
1152:
1149:
1147:
1144:
1143:
1141:
1137:
1131:
1128:
1126:
1123:
1119:
1116:
1115:
1114:
1111:
1110:
1108:
1104:
1098:
1095:
1093:
1090:
1088:
1085:
1083:
1080:
1078:
1075:
1073:
1070:
1069:
1067:
1065:
1061:
1055:
1052:
1050:
1047:
1045:
1042:
1040:
1037:
1036:
1034:
1030:
1024:
1021:
1019:
1016:
1014:
1011:
1009:
1006:
1004:
1001:
999:
998:Counting sort
996:
994:
991:
989:
986:
984:
981:
979:
976:
975:
973:
969:
963:
960:
958:
955:
953:
950:
948:
945:
944:
942:
938:
932:
929:
927:
924:
922:
919:
917:
914:
912:
909:
907:
904:
903:
901:
897:
891:
888:
886:
883:
881:
878:
876:
873:
871:
868:
866:
863:
861:
858:
857:
855:
853:
849:
843:
840:
838:
835:
833:
830:
828:
825:
823:
822:Odd–even sort
820:
818:
815:
813:
810:
809:
807:
803:
797:
794:
792:
789:
787:
786:X + Y sorting
784:
782:
779:
777:
774:
772:
771:Adaptive sort
769:
767:
764:
762:
759:
757:
754:
752:
749:
747:
744:
742:
739:
737:
734:
733:
731:
727:
723:
716:
711:
709:
704:
702:
697:
696:
693:
685:
684:0-13-022005-1
681:
677:
673:
669:
665:
661:
657:
653:
649:
645:
641:
640:
625:
620:
616:
609:
602:
597:
593:
587:
578:
573:
569:
565:
558:
552:
547:
541:
536:
530:
525:
517:
513:
506:
500:
495:
489:
484:
478:
474:
468:
464:
456:
454:
450:
446:
438:
435:
434:adaptive sort
431:
428:
425:
424:
423:
410:
408:
404:
402:
398:
394:
390:
388:
387:Class Library
385:
380:
377:
373:
366:
362:
360:
356:
349:
344:
341:
340:unstable sort
337:
334:
330:
325:
323:
319:
309:
307:
303:
299:
295:
290:
288:
284:
280:
279:Niklaus Wirth
269:
258:
252:
239:
234:
226:
222:
218:
214:
210:
202:
198:
196:
186:
184:
180:
176:
172:
168:
164:
160:
156:
152:
151:Musser (1997)
148:
143:
141:
137:
133:
129:
125:
121:
117:
113:
109:
106:
102:
98:
89:
85:
81:
77:
73:
71:
68:
64:
60:
56:
52:
50:
47:
43:
40:
37:
33:
30:
27:
23:
1086:
1064:Hybrid sorts
1013:Proxmap sort
926:Library sort
796:Quantum sort
675:
668:the original
655:
651:
614:
608:
599:
595:
586:
567:
557:
546:
535:
524:
515:
505:
494:
483:
477:David Musser
467:
442:
421:
405:
391:
381:
371:
363:
354:
345:
326:
315:
291:
286:
282:
275:
256:
250:
236:denotes the
232:
229:
224:
220:
216:
212:
208:
200:
192:
147:David Musser
144:
135:
131:
100:
96:
95:
79:
75:
58:
54:
1146:Stooge sort
988:Bucket sort
940:Merge sorts
812:Bubble sort
756:Inplacement
746:Total order
365:LLVM libc++
238:array slice
185:algorithm.
163:quickselect
157:, a hybrid
155:introselect
70:performance
49:performance
1092:Spreadsort
1054:Samplesort
1018:Radix sort
947:Merge sort
885:Cycle sort
870:Smoothsort
832:Gnome sort
577:2106.05123
459:References
336:stl_algo.h
189:Pseudocode
181:and a non-
46:Worst-case
1087:Introsort
1023:Flashsort
993:Burstsort
983:Bead sort
921:Tree sort
916:Splaysort
911:Shellsort
842:Quicksort
827:Comb sort
761:Stability
298:Sedgewick
264:array is
240:of items
209:procedure
201:procedure
195:quicksort
161:based on
120:logarithm
112:quicksort
97:Introsort
20:Introsort
1171:Category
1156:Bogosort
1151:Slowsort
865:Heapsort
646:(1997).
413:Variants
322:C++ sort
272:Analysis
179:in-place
173:for the
116:heapsort
1082:Timsort
636:General
418:pdqsort
217:else if
87:Optimal
67:Average
729:Theory
682:
568:GitHub
294:caches
183:stable
105:hybrid
1106:Other
751:Lists
572:arXiv
453:Boost
103:is a
39:Array
25:Class
680:ISBN
596:Rust
445:Rust
407:Java
382:The
346:The
331:C++
254:and
221:else
134:log
78:log
57:log
660:doi
619:doi
475:",
449:GAP
329:SGI
296:of
268:).
244:to
149:in
99:or
90:yes
1173::
656:27
654:.
650:.
598:.
594:.
570:.
566:.
514:.
455:.
447:,
436:),
393:Go
213:if
74:O(
53:O(
714:e
707:t
700:v
686:.
662::
627:.
621::
580:.
574::
518:.
471:"
372:n
369:2
355:n
352:2
283:n
266:A
262:A
257:A
251:A
246:j
242:i
233:A
205:2
136:n
132:n
130:(
128:O
82:)
80:n
76:n
61:)
59:n
55:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.