Microsoft Quick+insertion

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

 

[santosh]

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.

This question is more topical in one of the microsoft.public.*
newsgroups.

 

[Richard Heathfield]

Am said:

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

I doubt very much whether it was Microsoft which came up with this
improvement. It is true that they use it, but if you think it's their idea,
or if you want to know the details, I suggest you check "The Art of
Computer Programming Vol 3 - Sorting and Searching", by Donald E Knuth.

 

[Diomidis Spinellis]

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.

I doubt this is a Microsoft invention. Check out Bentley McIlroy's
classic paper "Engineering a Sort Function". Software---Practice and
Experience 23(11):1249--1269, November 1993. I located an online copy
at
http://www.enseignement.polytechniq.../Luc.Maranget/421/09/bentley93engineering.pdf

Also, the 1992-dated BSD Unix qsort implementation starts with the qsort
with an insertion sort if the numebr of elements is less than 7:

void
qsort(void *a, size_t n, size_t es,
int (*cmp)(const void *, const void*))
{
char *pa, *pb, *pc, *pd, *pl, *pm, *pn;

if (n < 7) {
for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
pl -= es)
swap(pl, pl - es);
return;
}
/* Recursive qsort implementation continues here */

 

[Am]

thank you very much Diomidis ,please keep in touch i may need u r help

 

[Am]

great u write books!,I am using fedora core 2 can you suggest me an RPM
package to know the amount of time a program spends in a
particular part of the program.

 

[Diomidis Spinellis]

great u write books!,I am using fedora core 2 can you suggest me an RPM
package to know the amount of time a program spends in a
particular part of the program.

gprof

Susan L. Graham, Peter B. Kessler, and Marshall K. McKusick. An
execution profiler for modular programs. Software: Practice &
Experience, 13:671–685, 1983.

 

[Am]

gprof, but can you post the link if possible

 

[Keith Thompson]

gprof, but can you post the link if possible

www.google.com

And please read <http://cfaj.freeshell.org/google/>.

 

[Mark McIntyre]

gprof, but can you post the link if possible

FCOL, STFW.
Mark McIntyre

 

[CBFalconer]

gprof, but can you post the link if possible

Meaningless. Include adequate context. See below for how on the
broken google interface to usenet.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

 

[pete]

Check out Bentley McIlroy's
classic paper "Engineering a Sort Function". Software---Practice and
Experience 23(11):1249--1269, November 1993. I located an online copy
at
http://www.enseignement.polytechniq.../Luc.Maranget/421/09/bentley93engineering.pdf

It has at least one mistake concerning the c programming language.

This footnote is wrong in what it says
about the pointer to void type, compeling casting:

† We have used simple parameter declarations for readability.
The official prototype in the ANSI standard header file,
<stdlib.h>, is6
void qsort(void *, size_t, size_t, int (*)(const void *, const void *));
This declaration can be used no more honestly than ours.
The first argument compels casting in the source of qsort;
the last compels casting in programs that call it.