mergesort. Reply

[Andrew J Bromage]

G'day all.

On Fri, Jun 28, 2002 at 09:44:11AM +0200, Ketil Z. Malde wrote:

> I, for one, am sorting expected, not worst-case, data :-)
> 
> <gripe>
> What's this obsession with worst-case behaviour anyway?

The best algorithm to use is the one which exploits known facts about
the data.  The converse is: The worst algorithm to use is the one whose
worst case behaviour happens on the sort of data you want to feed it.

So if, for example, you know that your data will cause expected-case
behaviour on average, more power to you.  If don't know that your data
will cause worst-case behaviour on average, shame on you for not being
obsessed enough.

Cheers,
Andrew Bromage