qsort() Appears Extremely Slow in Worst-Case Situations

MS-DOS                           | OS/2            | WINDOWS

The information in this article applies to:

• The C Run-time (CRT), included with:

      - Microsoft C for MS-DOS, versions 5.0, 5.1, 6.0, 6.0a, and 6.0ax
      - Microsoft C for OS/2, versions 5.1, 6.0, and 6.0a
      - Microsoft C/C++ for MS-DOS, version 7.0
      - Microsoft Visual C++ for Windows, versions 1.0 and 1.5
  

SUMMARY

When using qsort() in a worst-case situation (for example, the array is already sorted in reverse order), the qsort() library routine appears to take an extremely long time.

MORE INFORMATION

The qsort() routine provided by Microsoft was optimized for both speed and stack usage [stack space is important because qsort() is heavily recursive]. Therefore, in a worst-case situation, which could recurse up to the number of elements in the list, qsort() sacrifices speed for stack space. This behavior allows larger lists to be sorted without stack overflow problems. Furthermore, Microsoft's qsort() routine is very competitive in sorting random files, the type of array for which quick sorts are designed.

If used judiciously, Microsoft's qsort() is a very effective sort routine. In worst-case situations, Microsoft's qsort() is slower than some other sorting routines, but successfully sorts larger arrays without stack overflow problems.