Re: [Fwd: java/1895: Libjava: Arrays.sort doesn't work]

[Bryce McKinlay]

Mark Benvenuto wrote:

> Bryce McKinlay wrote:
>
> > Here's a bug report we received through the GCC bug tracking system.
> > It looks like the qsort implementation in java.util.Arrays is broken
> > for large arrays ;-(
> >
> > Does anyone know qsort well enough to take a look?
>
> Fixed. See Patch. The bugs was a problem that depends on the fact that our
> qsort implmentation does not happen arrays of length 7 very well. After
> recieving seven numbers from a first qsort, the qsort is suppose to divide
> and conquer the seven numbers. The problem is since the 7 numbers are not run
> through a proper divide (or med3) algorithm, the first number is picked (a
> worst case qsort scenario) _incorrectly_ and the next six numbers are
> processed by ultimately an insert sort. In a proper median algorithm, if the
> the first number was to be picked it would be the lowest one but in this case
> it could be any value. The fix is to handle the array size = 7 by adding an =
> sign to either the insertion sort routine or if statement wrapping the med3
> calls. Now back to HW :(

Thanks Mark - good catch! I found a link to the code upon which the
implementation is based:

http://www.cs.dartmouth.edu/~doug/source.html

I wonder what the original intent of the code was (and why it didn't work in our
version), since it appears that the value 7 is a special case, given the
explicit check for (n > 7) before the med3 code.

regards

  [ bryce ]