BUG: qsort reorders elements in already sorted array

[J. Johnston]

Corinna Vinschen wrote:
> 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.
> 

This is not a bug.

ANSI specifies the following for qsort:

   "If two elements compare as equal, their order in the sorted array is unspecified."

If you need a particular ordering of two elements, then the compare function has to
identify them as unequal.

I believe the 7 article case is caused by the fact that the code has if logic for < 7
and > 7, but not for == 7.

I am not seeing the extraneous values you are seeing.  This requires further investigation.

-- Jeff J.

> 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
>