Talk:Introsort

This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computer science Mid‑importance This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles Mid This article has been rated as Mid-importance on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}} Computing: Software / CompSci Low‑importance This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing articles Low This article has been rated as Low-importance on the project's importance scale. This article is supported by WikiProject Software (assessed as Low-importance). This article is supported by WikiProject Computer science (assessed as Mid-importance). Things you can help WikiProject Computer science with: edit history watch purge Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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)[reply]

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)[reply]

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]