Editing Introsort

{{Short description|Hybrid sorting algorithm}}
{{Infobox Algorithm
|class=[[Sorting algorithm]]
|image=
|caption=
|data=[[Array data structure|Array]]
|time=O(''n'' log ''n'')
|average-time=O(''n'' log ''n'')
|space=
|optimal=yes
}}

'''Introsort''' or '''introspective sort''' is a [[hybrid algorithm|hybrid]] [[sorting algorithm]] that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with [[quicksort]], it switches to [[heapsort]] when the recursion depth exceeds a level based on (the [[logarithm]] of) the number of elements being sorted and it switches to [[insertion sort]] 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 [[Big-O notation|O]](''n'' log ''n'') runtime due to the heap sort. Since the three algorithms it uses are [[comparison sort]]s, it is also a comparison sort.

Introsort was invented by [[David Musser]] in {{harvtxt|Musser|1997}}, in which he also introduced [[introselect]], a hybrid [[selection algorithm]] based on [[quickselect]] (a variant of quicksort), which falls back to [[median of medians]] and thus provides worst-case linear complexity, which is optimal. Both algorithms were introduced with the purpose of providing [[generic algorithm]]s for the [[C++ Standard Library]] which had both fast average performance and optimal worst-case performance, thus allowing the performance requirements to be tightened.<ref>"[http://www.cs.rpi.edu/~musser/gp/algorithms.html Generic Algorithms]", [[David Musser]]</ref>  Introsort is [[In-place_algorithm|in-place]] and a non-[[Sorting_algorithm#Stability|stable]] algorithm.

==Pseudocode==
If a heapsort implementation and partitioning functions of the type discussed in the [[quicksort]] article are available, the introsort can be described succinctly as

 '''procedure''' sort(A : array):
     maxdepth ← ⌊log<sub>2</sub>(length(A))⌋ × 2
     introsort(A, maxdepth)
 
 '''procedure''' introsort(A, maxdepth):
     n ← length(A)
     '''if''' n < 16:
         insertionsort(A)
     '''else if''' maxdepth = 0:
         heapsort(A)
     '''else''':
         p ← partition(A)  ''// assume this function does pivot selection, p is the final position of the pivot''
         introsort(A[1:p-1], maxdepth - 1)
         introsort(A[p+1:n], maxdepth - 1)

The factor 2 in the maximum depth is arbitrary; it can be tuned for practical performance. {{math|''A''[''i'':''j'']}} denotes the [[array slicing|array slice]] of items {{mvar|i}} to {{mvar|j}} including both {{math|''A''[''i'']}} and {{math|''A''[''j'']}}. The indices are assumed to start with 1 (the first element of the {{mono|A}} array is {{mono|A[1]}}).

==Analysis==
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. [[Niklaus Wirth]]'s variant uses the middle element to prevent these occurrences, degenerating to O(''n''<sup>2</sup>) 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 ''median-of-3 killer'' list that will cause dramatic slowdown of a quicksort based on this pivot selection technique.

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 [[CPU cache|caches]] of [[Robert Sedgewick (computer scientist)|Sedgewick]]'s delayed small sorting, where small ranges are sorted at the end in a single pass of [[insertion sort]]. He reported that it could double the number of cache misses, but that its performance with [[double-ended queue]]s 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.

==Implementations==
Introsort or some variant is used in a number of [[standard library]] sort functions, including some [[sort (C++)|C++ sort]] implementations.

The June 2000 [[Silicon Graphics|SGI]] C++ [[Standard Template Library]] [http://www.sgi.com/tech/stl/stl_algo.h stl_algo.h] implementation of [[unstable sort]] 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.

The [[GNU Standard C++ library]] is similar: uses introsort with a maximum depth of 2×log<sub>2</sub> ''n'', followed by an [[insertion sort]] on partitions smaller than 16.<ref>[https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a01027.html libstdc++ Documentation: Sorting Algorithms]</ref>

[[LLVM#C++_Standard_Library|LLVM libc++]] also uses introsort with a maximum depth of 2×log<sub>2</sub> ''n'', however the size limit for [[insertion sort]] is different for different data types (30 if swaps are trivial, 6 otherwise). Also, arrays with sizes up to 5 are handled separately.<ref>[https://github.com/llvm/llvm-project/blob/368faacac7525e538fa6680aea74e19a75e3458d/libcxx/include/__algorithm/sort.h#L272 libc++ source code: sort]</ref> Kutenin (2022) provides an overview for some changes made by LLVM, with a focus on the 2022 fix for quadraticness.<ref name="Kutenin-LLVM">{{cite web |last1=Kutenin |first1=Danila |title=Changing std::sort at Google’s Scale and Beyond |url=https://danlark.org/2022/04/20/changing-stdsort-at-googles-scale-and-beyond/comment-page-1 |website=Experimental chill |language=en |date=20 April 2022}}</ref>

The [[Microsoft .NET Framework]] [[Base Class Library|Class Library]], starting from version 4.5 (2012), uses introsort instead of simple quicksort.<ref>[http://msdn.microsoft.com/en-us/library/6tf1f0bc(v=vs.110).aspx Array.Sort Method (Array)]</ref>

[[Go (programming language)|Go]] uses a modification of introsort: for slices of 12 or less elements it uses [[insertion sort]], and for larger slices it uses [[#pdqsort|pattern-defeating quicksort]] and more advanced median of three medians for pivot selection.<ref>[https://github.com/golang/go/blob/go1.20.3/src/sort/zsortfunc.go#L61 Go 1.20.3 source code]</ref> Prior to version 1.19 it used shell sort for small slices.

[[Java (programming language)|Java]], 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.<ref>[https://github.com/openjdk/jdk/blob/jdk-14-ga/src/java.base/share/classes/java/util/DualPivotQuicksort.java#L178 Java 14 source code]</ref>

== Variants ==

=== pdqsort ===
Pattern-defeating quicksort (pdqsort) is a variant of introsort developed by Orson Peters, incorporating the following improvements:<ref>{{cite web |last1=Peters|first1=Orson R. L. |title=orlp/pdqsort: Pattern-defeating quicksort. |url=https://github.com/orlp/pdqsort |website=GitHub |year=2021 |language=en |arxiv=2106.05123}}</ref>
* Median-of-three pivoting,
* "BlockQuicksort" partitioning technique to mitigate branch misprediction penalities,
* Linear time performance for certain input patterns ([[adaptive sort]]),
* Use element shuffling on bad cases before trying the slower heapsort.
* Improved adaptivity for low-cardinality inputs

Pdqsort is used by [[Rust (programming language)|Rust]], [[GAP (computer algebra system)|GAP]],<ref>{{cite web |title=slice.sort_unstable(&mut self) |url=https://doc.rust-lang.org/std/primitive.slice.html#method.sort_unstable |website=Rust |quote=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 a fixed seed to always provide deterministic behavior.}}</ref> and the C++ library [[Boost (C++ libraries)|Boost]].<ref>{{cite conference |last1=Lammich |first1=Peter |title=Efficient Verified Implementation of Introsort and Pdqsort |doi-access=free |conference=IJCAR 2020: Automated Reasoning |date=2020 |volume=12167 |pages=307–323 |doi=10.1007/978-3-030-51054-1_18}}</ref>

=== fluxsort ===
fluxsort is a stable variant of introsort incorporating the following improvements:<ref>{{cite web |last1=van den Hoven|first1=Igor |title=fluxsort |url=https://github.com/scandum/fluxsort |website=GitHub |year=2021 |language=en }}</ref>
* branchless sqrt(n) pivoting
* Flux partitioning technique for stable partially-in-place partitioning
* Significantly improved smallsort by utilizing branchless bi-directional parity merges
* A fallback to quadsort, a branchless bi-directional mergesort, significantly increasing adaptivity for ordered inputs

Improvements introduced by fluxsort and its unstable variant, crumsort, were adopted by crumsort-rs, glidesort, ipnsort, and driftsort. The overall performance increase on random inputs compared to pdqsort is around 50%.<ref>{{cite web |last1=van den Hoven|first1=Igor |title=crumsort |url=https://github.com/scandum/crumsort|website=GitHub |year=2022 |language=en }}</ref><ref>{{cite web |last1=Tiselice|first1=Dragoș |title=crumsort-rs |url=https://github.com/google/crumsort-rs |website=GitHub |year=2022 |language=en }}</ref><ref>{{cite web |last1=Peters|first1=Orson|title=Glidesort: Efficient In-Memory Adaptive Stable Sorting on Modern Hardware |url=https://archive.fosdem.org/2023/schedule/event/rust_glidesort/ |year=2023 |language=en }}</ref><ref>{{cite web |last1=Bergdoll|first1=Lukas|title=ipnsort: an efficient, generic and robust unstable sort implementation. |url=https://github.com/Voultapher/sort-research-rs/blob/main/writeup/ipnsort_introduction/text.md |year=2024 |language=en }}</ref><ref>{{cite web |last1=Bergdoll|first1=Lukas|title=driftsort: an efficient, generic and robust stable sort implementation. |url=https://github.com/Voultapher/sort-research-rs/blob/main/writeup/driftsort_introduction/text.md |year=2024 |language=en }}</ref>

==References==
{{reflist}}

===General===
{{refbegin}}
* {{Cite journal | last = Musser | first = David R. | author-link = David Musser | title = Introspective Sorting and Selection Algorithms | url = http://www.cs.rpi.edu/~musser/gp/introsort.ps| doi = 10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-# | journal = Software: Practice and Experience | volume = 27 | issue = 8 | pages = 983–993 | year = 1997 | archive-url = https://web.archive.org/web/20230307185457/http://www.cs.rpi.edu/~musser/gp/introsort.ps | archive-date = 7 March 2023| url-access = subscription }}
* Niklaus Wirth. ''Algorithms and Data Structures''. Prentice-Hall, Inc., 1985. {{ISBN|0-13-022005-1}}.
{{refend}}

{{sorting}}

[[Category:Comparison sorts]]
[[Category:Articles with example pseudocode]]