Re: Ada Components - GRACE Lists (Sorting them)

["Chad R. Meiners" <crmeiners@hotmail.com>]

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.

Comments?

-CRM