[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: cowboyd
Subject: Re: [Fwd: java/1895: Libjava: Arrays.sort doesn't work]
Date: Wed, 7 Feb 2001 10:47:00 -0500

It could have been an attempt at an optimization. There is a threshold with
quick sort such that below a certain number of elements, the probability is
higher that it will complete faster with an insertion sort. This threshold
is mathematically discoverable, and I once saw it derived in a probability
course. In fact, I think it was 12 (but I can't be sure)


                    McKinlay             To:     Mark Benvenuto 
                    <address@hidden        cc:     Classpath <address@hidden>   
          >           Subject:     Re: [Fwd: java/1895: 
Libjava: Arrays.sort doesn't work]      
                    Sent by:                                                    
                    04:40 PM                                                    

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
> qsort implmentation does not happen arrays of length 7 very well. After
> recieving seven numbers from a first qsort, the qsort is suppose to
> and conquer the seven numbers. The problem is since the 7 numbers are not
> through a proper divide (or med3) algorithm, the first number is picked
> worst case qsort scenario) _incorrectly_ and the next six numbers are
> processed by ultimately an insert sort. In a proper median algorithm, if
> the first number was to be picked it would be the lowest one but in this
> 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
> calls. Now back to HW :(

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

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.


  [ bryce ]

Classpath mailing list

reply via email to

[Prev in Thread] Current Thread [Next in Thread]