Editing Introsort (section)

==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>