By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,946 Members | 773 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,946 IT Pros & Developers. It's quick & easy.

quick+insertion details by microsoft(1997)

P: n/a
Am
hi
i came to know that microsoft improved the efficiency of quick sort
by using a cutoff
of 8 elements and continuing with insertion sort then, do anybody have
the details about it
please contant me.

Apr 14 '06 #1
Share this Question
Share on Google+
5 Replies


P: n/a
"Am" <ma*********@gmail.com> wrote in message
news:11**********************@g10g2000cwb.googlegr oups.com...
: i came to know that microsoft improved the efficiency of quick sort
: by using a cutoff
: of 8 elements and continuing with insertion sort then, do anybody have
: the details about it
: please contant me.

The enhanced algorithm is called *introsort*, designed by David Musser.
http://en.wikipedia.org/wiki/Introsort
It is often used to implement std::sort.

--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Brainbench MVP for C++ <> http://www.brainbench.com
Apr 14 '06 #2

P: n/a
Ivan Vecerina wrote:
"Am" <ma*********@gmail.com> wrote in message
news:11**********************@g10g2000cwb.googlegr oups.com...
: i came to know that microsoft improved the efficiency of quick sort
: by using a cutoff
: of 8 elements and continuing with insertion sort then, do anybody have
: the details about it
: please contant me.

The enhanced algorithm is called *introsort*, designed by David Musser.
http://en.wikipedia.org/wiki/Introsort
It is often used to implement std::sort.


That's a different enhancement.

--

Pete Becker
Roundhouse Consulting, Ltd.
Apr 14 '06 #3

P: n/a
Am wrote:
hi
i came to know that microsoft improved the efficiency of quick sort
by using a cutoff
of 8 elements and continuing with insertion sort then, do anybody have
the details about it
please contant me.


You've just given the details. What's the question? (Note that just
about any algorithms book will talk about this enhancement)

--

Pete Becker
Roundhouse Consulting, Ltd.
Apr 14 '06 #4

P: n/a
Am
Thank you pete,but what i need is the internal details ie the
performance of algorithm for various input size and type.

Apr 15 '06 #5

P: n/a
Am
but intosort ,as you said begins with quick sort and ends up utilising
heap sort but i require info regarding quick and insertion sort

Apr 15 '06 #6

This discussion thread is closed

Replies have been disabled for this discussion.