Newsgroup: comp.lang.c

Am wrote:
>    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.polytechnique.fr/profs/informatique/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 */

-- 
Diomidis Spinellis
Code Quality: The Open Source Perspective (Addison-Wesley 2006)
http://www.spinellis.gr/codequality

Unless otherwise expressly stated, all original material on this page created by Diomidis Spinellis is licensed under a Creative Commons Attribution-Share Alike 3.0 Greece License.