Is Ms vc6 qsort known to be 'smart' about already sorted array?

Posted on 2002-04-29
Medium Priority
Last Modified: 2013-11-20
Is Ms vc6 qsort known to be 'smart' about already sorted array?

I'm getting ready to do some sorting of a small'ish array. (300 to 1000 elements). In general, it will already be sorted, or almost sorted.  My understanding is that some implementations of qsort become quadratic with an array that is already sorted.  Does anyone know specifically if this applies to MicroSoft's implementation in visual c++ 6, sp5?  Preferrably, this would include a link to something authoritative with, ideally, a test program.

I could write a quick 'proof-of-concept' program, but would rather ask this forum.

A related question ... my impression is that a variant of a quadratic sort algorithm turns out to be 'good enough' for almost sorted arrays.  Is this the 'shell' sort?  Can some 'smart' implementations of qsort detect an already (or almost) sorted list and use another algorithm for this partition?  Or use a simple quadratic sort variant when the partition get small?

Question by:ee-user
  • 2

Accepted Solution

snoegler earned 200 total points
ID: 6982108
You can take a look at qsort.c (installed with the MSVC RTL source code) in VC98\CRT\SRC\QSORT.c

Basically, it decides whether the array is short (8 elements) and does an insertion sort if that is the case.

Otherwise, it takes the middle element as median. Original comment from the source code:

        /* First we pick a partititioning element.  The efficiency of the
           algorithm demands that we find one that is approximately the
           median of the values, but also that we select one fast.  Using
           the first one produces bad performace if the array is already
           sorted, so we use the middle one, which would require a very
           wierdly arranged array for worst case performance.  Testing shows
           that a median-of-three algorithm does not, in general, increase
           performance. */

Author Comment

ID: 6982643

Thanks for the reply.  I didn't choose the option to install source code during VisStudio installation .. perhaps I should have :-(

Based on the comment you provide, MicroSoft's implementation of qsort looks at least adequately 'smart'.

Expert Comment

ID: 6983109

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Introduction: Finishing the grid – keyboard support for arrow keys to manoeuvre, entering the numbers.  The PreTranslateMessage function is to be used to intercept and respond to keyboard events. Continuing from the fourth article about sudoku. …
In this post we will learn different types of Android Layout and some basics of an Android App.
This video will show you how to get GIT to work in Eclipse.   It will walk you through how to install the EGit plugin in eclipse and how to checkout an existing repository.
Planning to migrate your EDB file(s) to a new or an existing Outlook PST file? This video will guide you how to convert EDB file(s) to PST. Besides this, it also describes, how one can easily search any item(s) from multiple folders or mailboxes…

600 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question