Re: Ada Components - GRACE Lists (Sorting them)

[Thomas Wolf <t_wolf@angelfire.com>]

crmeiners@hotmail.com wrote:
> I remembering that there was a discussion about using quicksort for these
> list components.  There was naturally concern about the O(n^2) worst case
> performance.  If people are still worried about this issue, I have a
> solution that guarantees that quicksort worst case is O(n*log n).  Before
> any of you spill your coffee ;-) there is a hefty constant involved that
> makes this modified quicksort slower on average than heapsort (maybe
> mergesort sort also but it doesn't take more space that mergesort).  Anyway
> the idea is to choose the median of each list (sublist) in linear time.
> There happens to be a 'well known algorithm' for this.  The only drawback is
> a hit on the constant.  I figure it might not be too bad of a price to pay,
> though.

For lists, mergesort is not a bad choice: worst-case O(n*log n), and
the constant factor compared to a quicksort on arrays is not that bad.

If you want a quicksort with worst-case O(n*log n), check out 
introspective sort. Performs just as well as quicksort, but
avoids the quadratic worst case. Basically it counts the nesting
depth and switches to heapsort if that count gets significantly
greater than log n, assuming that in this case, it has hit a worst-
case input for quicksort. Because it counts the nesting depth, it
can get by with a standard median-of-three pivot selection; no need
for fancy things like choosing the true median.

-- 
-----------------------------------------------------------------
Thomas Wolf                          e-mail: t_wolf@angelfire.com