ENH add an introsort implementation

[hayd]

This is an implementation from the pseudo-code in Musser's paper.

I haven't done any performance testing, no doubt there is optimization to do here e.g. @inbounds and something better for index_of_median_of_three (which atm is terrible)...

[stevengj]

What's the advantage of introsort?

[kmsquire]

I haven't looked at this yet, but generally, introsort uses quick sort, but keeps track of recursion depth, and if it reaches a certain depth, switches to a different algorithm with guaranteed worst case depth of O(log N).

It's a good algorithm to have available.

On Monday, October 27, 2014, Steven G. Johnson [email protected] wrote:

What's the advantage of introsort?

— Reply to this email directly or view it on GitHub https://github.com/JuliaLang/SortingAlgorithms.jl/pull/7#issuecomment-60618924 .

[xiaodaigh]

it's been more than 5 years. close it, merge it, or start another repo

[nalimilan]

There's an unresolved comment above that somebody needs to address (and also needs a rebase). (BTW, necro-posting generally isn't useful if you're not volunteering to work on PRs yourself.)