BUG: qsort() Sorts Huge String Arrays > 64K Incorrectly

The information in this article applies to:

   The C Run-time (CRT) included with
     - Microsoft Visual C++ for Windows, version 1.5 and 1.51

SYMPTOMS

Using the C Run-time function qsort() to sort a two-dimensional character array that is greater than 64K in size may generate incorrect results such as missing the first element in the result, or causing the computer to hang (stop responding). This happens if a two-dimensional character array is used in the huge memory model or if a huge pointer is used in the other memory models.

RESOLUTION

To correct the problem, use one of these workarounds:

• Instead of using a two-dimensional character array, use an array of structure that contains a field of a character array. See the example below in the Sample Code section of this article.

  - or -

• If the string information is of a numerical type, you might try sorting the numbers as numbers. Then store them as strings if necessary.

STATUS

Microsoft has confirmed this to be a bug in the Microsoft products listed at the beginning of this article. We are researching this problem and will post new information here in the Microsoft Knowledge Base as it becomes available.

MORE INFORMATION

The sample code below reproduces the problem. To work around the problem, compile the code WITHOUT switch /D"_PROBLEM".

Sample Code

/* Compile options needed: /AH /D"COLUMN=36" /D"_PROBLEM"
*/

/* -- test.c -- */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>

#define ROW ( (0xffff/COLUMN) + 1 )    /* ( 65535/COLUMN ) + 1 */

char TestString[ROW][COLUMN];

int cmp( const void *c1, const void *c2 );
                                 /* User defined sort function */
void main()

   int i;

   for ( i=0; i<ROW; i++ )
   {

     sprintf( TestString[i], "%6d\n", rand() );

     sprintf( TestString[i].string, "%6d\n", rand() );

   }

   qsort( (void*)TestString, (size_t)ROW, (size_t)COLUMN, cmp );

   qsort( (void*)TestString, (size_t)ROW, sizeof(struct Test), cmp );

   for ( i=0; i<ROW; i++ )
   {

     if ( TestString[i][0] == '\0' )
        printf("TestString[%d] is empty.\n", i );
     else
        printf("TestString[%d] = %s", i, TestString[i] );

     if ( TestString[i].string[0] == '\0' )
        printf("TestString[%d] is empty.\n", i );
     else
        printf("TestString[%d] = %s", i, TestString[i].string );

   }

int cmp( const void *c1, const void *c2 )

   return strcmp( c1, c2 );

   return strcmp( ((struct Test*)c1)->string,
                  ((struct Test*)c2)->string
                );