Path: csiph.com!aioe.org!news.mixmin.net!border2.nntp.ams1.giganews.com!nntp.giganews.com!buffer2.nntp.ams1.giganews.com!buffer1.nntp.ams1.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail NNTP-Posting-Date: Wed, 21 Dec 2016 17:34:05 -0600 From: Gareth Owen Newsgroups: comp.lang.c++ Subject: Re: Qucksort for Linked List References: <87d1gue00s.fsf@gmail.com> <42d98296-3339-4814-8ba9-d8d71607e5bc@googlegroups.com> <49d489dd-7c85-4bbf-a6a3-1d3e8034d6b0@googlegroups.com> <87poklozd5.fsf@gmail.com> <7tidnZiIoabdRsfFnZ2dnUU7-dmdnZ2d@giganews.com> <87lgv9ovgn.fsf@gmail.com> <48mdnel_q6ZhccfFnZ2dnUU7-VGdnZ2d@giganews.com> Date: Wed, 21 Dec 2016 23:34:04 +0000 Message-ID: <87bmw4n9g3.fsf@gmail.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux) Cancel-Lock: sha1:Col3CjgrSEST30qE0qey7GWezNY= MIME-Version: 1.0 Content-Type: text/plain Lines: 33 X-Usenet-Provider: http://www.giganews.com X-Trace: sv3-SppaPyjbeTX8LOwjKgz3SEyL4yZmUNiyBXHobzfcN1dZhsRd/WWXBD/KFhgDJs52A867/NPwEbykT0A!Nfn82WTE1Y6giwHt/AwImWqGEkIoRA8xxyHM3rBvliIX+1bdbt0FL+cu6gWTxu2+DNzM 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: 2914 Xref: csiph.com comp.lang.c++:47496 Mr Flibble writes: >>> So fuck off; I am right and you are wrong. >> >> Not true. Maths isn't a strong point, is it? > > This has nothing to do with maths; this is to do with analysing > algorithmic complexity. *facepalm* Analysing algorithms is a discipline of mathematics. > See Wikipedia above. Nevertheless, if you were capable of doing the mathematics, you'd see that the average case performance is still O(N log N). The proof that quicksort is O(N log N) on average is independent of the underlying data structure. The reason for this is that choosing a sane pivot (median of nine say) is O(n), and you can do a fixed number of different O(n) at each recursive step you don't change the algorithmic complexity (but you might screw up the constants so badly that it runs much slower than mergesort). The Wikipedia section on "Selection based pivoting" describes a scheme based on this fact. Note also that proviso in Wikipedia is about *stable* quicksort, and std::list::sort is *not* required to be stable. Note also, that some time ago I mentioned that mergesort is often preferred because it is stable, where quicksort isn't. > /Flibble PS: Your killfile is broken