Re: perl builtin sort has bad worst-case behavior

[Tom Hughes <tom@compton.nu>]

In message <200001130626.BAA21321@monet.op.net>
          Mark-Jason Dominus <mjd@Op.Net> wrote:

> You can complain that the organ-pipe input is artificial, but I knew
> to try it because an innocent user tripped over the same problem in
> that qsort implementation I wrote.  *ALL* qsort implementations will
> go quadratic on some inputs (which is why my external sorts now use
> merge-sort or radix-sort implementations, which don't), but they don't
> have to do so on inputs as common as organ-pipe data.

The best choice of sort to maintain quicksort performance in most
cases but avoid quicksort performance in the worst cases is likely
to be introsort which is O(n log n) in the worst case as well as the
average but still maintains the low constant factors of quicksort
in most cases.

Tom

-- 
Tom Hughes (tom@compton.nu)
http://www.compton.nu/
...Wibble Wobble Fishcakes.

---

References to:

Mark-Jason Dominus <mjd@Op.Net>

---

[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index][Thread Index][Top&Search][Original]

---