Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.supernews.com!news.supernews.com.POSTED!not-for-mail
NNTP-Posting-Date: Wed, 10 Jul 2013 05:44:12 -0500
Sender: Andrew Haley <aph@zebedee.pink>
From: Andrew Haley <andrew29@littlepinkcloud.invalid>
Subject: Re: Simple Sort - the smallest sorting routine?
Newsgroups: comp.lang.forth
References: <a90e9108-640c-4d83-ad22-b21462a47668@googlegroups.com> <UI-dnWjgNLTHj0XMnZ2dnUVZ_oGdnZ2d@supernews.com> <2013Jul6.153838@mips.complang.tuwien.ac.at> <5PednZKx29YYr0XMnZ2dnUVZ_qudnZ2d@supernews.com> <2013Jul7.115901@mips.complang.tuwien.ac.at> <vOWdnbVSbJX7y0TMnZ2dnUVZ_uWdnZ2d@supernews.com> <2013Jul7.141859@mips.complang.tuwien.ac.at> <wKKdnVVMtarQT0fMnZ2dnUVZ_vednZ2d@supernews.com> <2013Jul9.162517@mips.complang.tuwien.ac.at> <vKCdnXJ_newGhEDMnZ2dnUVZ_rednZ2d@supernews.com> <2013Jul10.122911@mips.complang.tuwien.ac.at>
User-Agent: tin/1.9.2-20070201 ("Dalaruan") (UNIX) (Linux/3.8.13-100.fc17.x86_64 (x86_64))
Message-ID: <hKCdnW36SZ5hp0DMnZ2dnUVZ_gOdnZ2d@supernews.com>
Date: Wed, 10 Jul 2013 05:44:12 -0500
Lines: 24
X-Trace: sv3-6LhRI+t33N6EOLFwSEN9bLEW10OrUqHwMdYlWWLnlRRCzq2MIykhJzXlFhjH6Sp4u9nFqSVyOa+vMbt!7oqGkDMm1xOj+e0TiOiwnAAb+74MMYS0Td+EStLXDp1i3jP5ScDTww79LH4bvPKvQTFrw05qwdd1!+6Hbzj0a8Do=
X-Complaints-To: www.supernews.com/docs/abuse.html
X-DMCA-Complaints-To: www.supernews.com/docs/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 2622
Xref: csiph.com comp.lang.forth:24354

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>> 
>>> So median-of-3 does not buy any speed compared to middle pivot, it's
>>> just more complex; same with swapping.
>>
>>I think the argument is that it is a small win on average: it doesn't
>>add much time in the random case, but it does avoid some degenarate
>>behaviour.
> 
> What degenerate behaviour does it avoid?  Sure, you can construct
> input that shows quadratic behaviour for middle pivot, but you can
> also construct input that shows quadratic behaviour for the
> median-of-3 variant you measured.  The probability that inputs with
> quadratic behaviour will occur by accident is vanishingly small with
> either pivot selection method.

Right, so the question is how much more probable the behaviour is for
middle pivot than median-of-3.  With random data, I believe it is at
least three times more probable.  With other datasets, the probability
will vary.

Andrew.