quick+insertion details by microsoft(1997)

[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.

 

[Ivan Vecerina]

: 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.

 

[Pete Becker]

: 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]

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)

 

[Am]

Thank you pete,but what i need is the internal details ie the
performance of algorithm for various input size and type.

 

[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