BUG: qsort reorders elements in already sorted array

[Corinna Vinschen]

Hi,

I found that there's a bug in newlib's implementation of qsort, which
results in more or less unreliable reordering of things.

The problem seem to occur in border cases only.  The border case I
have is tin, the news reader.  I've build the latest developer version
of tin, 1.5.18, and found that the ordering of threads in a newsgroup
was correct, except to my surprise that the first and the last thread
had exchanged their place.  As a figure, the order wasn't

  0 1 2 3 4 5 6 7 8 9

but

  9 1 2 3 4 5 6 7 8 0

This happened in all newsgroups, except for one, which had only 7 articles.

But what's the border case here?  By default, the threads are ordered
by "score", a function of the state of the articles in the thread.
Unfortunately it's very typical, that the score of all threads is 0.
As a result, qsort's compare function returns 0 for all comparisons
between elements in the array.  Even worse, since the array of articles
is already ordered by date before, it's very likely that the threads are
pretty much already in the right order before calling qsort on them.

To test that phenomenon, I created a very simple test case:

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

    int
    cmp (const void *p1, const void *p2)
    {
      return 0;
    }

    int
    main (int argc, char **argv)
    {
      int i, *a, size = 10;

      if (argc > 1 && atoi(argv[1]) > 0)
	size = atoi(argv[1]);
      a = (int *) malloc (sizeof(int) * size);
      for (i = 0; i < size; ++i)
	a[i] = i;
      qsort (a, size, sizeof(int), cmp);
      for (i = 0; i < size; ++i)
	printf ("%d ", a[i]);
      printf ("\n");
      return 0;
    }


which allows to reproduce the problem with a minimum of code.  Let's
have a look into the results (here on Cygwin):

    $ gcc -g sort.c -o sort

    $ ./sort 5
    0 1 2 3 4

    $ ./sort 6
    0 1 2 3 4 5 

    $ ./sort 7
    0 1 2 3 4 5 6 

    $ ./sort 8
    2945 1 2 3 4 5 6 7 

Huh?

    $ ./sort 9
    2945 1 2 3 4 5 6 7 8 

What's that?

    $ ./sort 10
    9 1 2 3 4 5 6 7 8 0 

Ah, now the effect described above is visible...

    $ ./sort 11
    10 1 2 3 4 5 6 7 8 9 0

    $ ./sort 50
    49 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 0 

...and reproducible for any number of elements >= 10.

Unfortunately I haven't worked out what the actual problem in the
qsort implementation is.  I'm still debugging but I thought, somebody
with a more intimate relation to qsort might have a clue.  Btw., I'm
suspecting the med3 function to scamble things when the compare function
returns 0 for all tested elements pl, pm, pn.


Corinna

-- 
Corinna Vinschen
Cygwin Developer
Red Hat, Inc.
mailto:vinschen@redhat.com