From: Wolfgang Hoschek <whoschek@lb...>  20041213 07:21:44

In theory, *any* quicksort flavour can be driven to quadratic time. But=20= one key feature of BMQ is that it is highly resilient for all practical=20= purposes. I just checked the "killer sequences" given in the paper against BMQ.=20 For example using a sequence with 10000 elements. Results: No dramatic degradation. Number of comparisons remains N log=20 N. If the comparison function is cheap, BMQ is 2x faster than mergesort=20= in wallclock time. If, on the other hand, the comparison function is=20 very expensive, then mergesort is 3x faster than BMQ. Wolfgang. On Dec 12, 2004, at 9:42 PM, Wolfgang Hoschek wrote: > Dimitre, > > If you have a production quality implementation of this algorithm,=20 > feel free to send it over to me or Mike so I can run it through my=20 > sort algo testbed, checking correctness and performance under a range=20= > of inputs. Make sure it conforms to Mike's quicksort interface. > > The paper you cite claims: > >> Previous attempts to protect against the worst case by improving the=20= >> way quicksort chooses pivot elements for partitioning have increased=20= >> the average computing time too much =96 one might as well use = heapsort > > This is not my experience. BentleyMcIlroy Quicksort (BMQ) does not=20 > significantly increase the average computing time. Rather, it fully=20 > retains quicksorts speed. Everything I've seen tells that it is ALWAYS=20= > faster than Mike's simple quicksort, sometimes just a little,=20 > sometimes by a large constant factor, and in rare cases by a full time=20= > complexity level. BMQ is theoretically sound, rendering degradation to=20= > O(N^2) extremely unlikely for all practical purposes, and it is=20 > implementable in a straightforward and very efficient manner. Today I=20= > just did some more minor tweaks to its implementation without changing=20= > the algorithmic properties, gaining a better constant factor. > > As a result, BMQ is a credible alternative to mergesort (or heapsort)=20= > even in mission critical DBMS apps where quadratic performance is=20 > considered intolerable. > > BTW, select parts of the tuned mergesort I proposed to Mike as a=20 > worstcase alternative have their origins in JAL, which in turn was a=20= > partial port of STL to Java (many years ago). > > Wolfgang. > > On Dec 12, 2004, at 8:26 PM, saxonhelprequest@...=20= > wrote: > >> I'd recommend looking into Introspection Sort, which is implemented=20= >> in the >> C++ STL. It uses the full strength of QuickSort, but recognizes the=20= >> worst >> case and then uses another algorithm, which behaves well. >> >> http://www.oopl.com/Papers/IntroSortSPE1997.pdf >> >> http://www.sgi.com/tech/stl/stl_algo.h >> >> >> Cheers, >> Dimitre. > 