Talk:Introsort

Implementation

Does anyone have an implementation of this to add to the article? It sounds like a simple cutoff, but I think it would help clarify what InroSort actually does.

What's a "median-of-3" and what's a "killer dataset"? --71.71.238.231 07:06, 15 June 2006 (UTC)

A median-of-3 pivot selection algorithm takes the median of the first, last, and middle element of the list. A median-of-3 killer dataset is one which is designed specifically to cause the median-of-3 pivot selection algorithm to exhibit worst-case behavior. This is all, admittedly, quite impossible to divine - I should expand the article - but you can find some additional information at quicksort. Deco 08:24, 15 June 2006 (UTC)

What is introspective about the introsort? --User:Taejo|대조 11:41, 8 February 2007 (UTC)

C++ Standard Library

What is the purpose of the last paragraph of this article? It currently reads:

"The C++ STL implementations generally significantly (several times as fast) outperform the C implementation because they are implemented to allow inlining, while the generic C equivalent must use function calls for comparisons. This advantage could be compensated for by using custom versions of the C sort function, at the cost of losing the advantage of a totally generic library function."

This is a total tangent and has absolutely nothing to do with anything. Any objections to simply deleting this part? Promit 23:40, 7 April 2007 (UTC)

On second thought, I'll delete it now, since I'm not sure how many people are active here. If someone has a problem with it, feel free to revert and take it up here. Promit 23:41, 7 April 2007 (UTC)

Introselect

There ought be a link to Musser's Introselect. Introselect is used to solve finding the kth element out of n elements without having to sort all the n elements. A variation of quicksort called quickselect is used which partitions the elements and zooms in on the partition which has the kth element. The problem is that like quicksort, it has a worse case. Quickselect has average-case of O(n) and worse-case of O(n²). Intraselect has a average and worse-case of O(n) Stephen Howe 21:30, 4 May 2007 (UTC)

Sedgewick's delayed small sorting

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 caches of 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 queues 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.

It sounds like we need a page for "Sedgewick's delayed small sorting". Or at least an external link expanding on the subject... It is used as though it is a well-known concept. Is it? — Preceding unsigned comment added by 151.183.0.36 (talk) 09:30, 20 November 2013 (UTC)

Citation about GNU standard C++ library

If you look at std_algo.h line 5243, it's not hard to see that it uses introsort, even if you are not a programmer. For C++ programmers, it's trivial to see that it sorts until it reaches depth std::__lg(__last - __first) * 2, then does a std::__final_insertion_sort(__first, __last, __comp);, so it proves the paragraph. However, I'm not sure that this satisfies the requirements to be a citation. — Preceding unsigned comment added by 123.114.54.9 (talk) 12:10, 23 January 2015 (UTC)

Pseudocode

The first paragraph states that "[...] it switches to insertionsort [...]" yet the Pseudocode section shows no indication of that happening ? — Preceding unsigned comment added by 50.111.5.202 (talk) 02:40, 16 December 2019 (UTC)

I agree, there were several problems in the pseudocode, I changed it. Would be great if someone could double check it.EduardoW (talk) 07:41, 25 March 2022 (UTC)