Introsort
Introsort or introspective sort is a 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 O(n log n) runtime due to the heap sort. Since the three algorithms it uses are comparison sorts, it is also a comparison sort.
Wikipage redirect
C++ Standard LibraryComparison sortDavid MusserHeapsortHybrid algorithmIntro sortIntroselectIntrospection sortIntrospective sortIntuitive–instrumental griefList of algorithmsList of terms relating to algorithms and data structuresQuicksortSelection algorithmShellsortSort (C++)Sorting algorithmSpreadsortTime complexity
Link from a Wikipage to another Wikipage
primaryTopic
Introsort
Introsort or introspective sort is a 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 O(n log n) runtime due to the heap sort. Since the three algorithms it uses are comparison sorts, it is also a comparison sort.
has abstract
Introsort nebo také introspekt ...... en prvek, a v druhé n-1 prvků.
@cs
Introsort or introspective sor ...... rt is in place and not stable.
@en
Introsort ou introspective sor ...... e complexité dans le pire cas.
@fr
Introsort ou introspective sor ...... introspecção ou "Introselect".
@pt
Introsort или интроспективная ...... ржащих менее чем 16 элементов.
@ru
Sortowanie introspektywne (ang ...... lgorytmu sortowania szybkiego.
@pl
イントロソート(英: introsort)は、 が1997年 ...... う方式である。挿入ソートに切り替わる再帰の深さは16だった。
@ja
内省排序(英語:Introsort)是由David Muss ...... 省排序算法。在此实现中,切换到插入排序的数据量阈值为16个。
@zh
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
1,019,174,763
Link from a Wikipage to another Wikipage
average-time
O
@en
class
optimal
yes
@en
time
O
@en
wikiPageUsesTemplate
hypernym
type
comment
Introsort nebo také introspekt ...... en prvek, a v druhé n-1 prvků.
@cs
Introsort or introspective sor ...... it is also a comparison sort.
@en
Introsort ou introspective sor ...... e complexité dans le pire cas.
@fr
Introsort ou introspective sor ...... uma ordenação por comparação.
@pt
Introsort или интроспективная ...... ортировок на основе сравнений.
@ru
Sortowanie introspektywne (ang ...... lgorytmu sortowania szybkiego.
@pl
イントロソート(英: introsort)は、 が1997年 ...... きる。例えば、そのようなリストを使ったDoS攻撃がありうる。
@ja
内省排序(英語:Introsort)是由David Muss ...... 围内数据的排序由Sedgewick提出的小数据排序算法完成。
@zh
label
Intro sort
@pt
Introsort
@cs
Introsort
@de
Introsort
@en
Introsort
@fr
Introsort
@ru
Sortowanie introspektywne
@pl
イントロソート
@ja
内省排序
@zh