Path: csiph.com!aioe.org!news.mixmin.net!border2.nntp.ams1.giganews.com!nntp.giganews.com!buffer2.nntp.ams1.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 19 Dec 2016 13:31:43 -0600
From: Gareth Owen <gwowen@gmail.com>
Newsgroups: comp.lang.c++
Subject: Re: Qucksort for Linked List
References: <dfa00771-7568-443b-ab45-174f0749a176@googlegroups.com> <o2m7v7$2s1e$1@adenine.netfront.net> <a8ydnTLbnp2tcNPFnZ2dnUU7-bGdnZ2d@neganews.com> <o2o7q6$2prn$1@adenine.netfront.net> <yuudnRfdreaAqM3FnZ2dnUU7-LudnZ2d@giganews.com> <o2rcld$nhd$1@dont-email.me> <87d1gue00s.fsf@gmail.com> <mrSdnUOdRsH4JczFnZ2dnUU7-TGdnZ2d@giganews.com> <o30hk4$112$1@adenine.netfront.net> <ANqdnaKugKq-78nFnZ2dnUU7-VWdnZ2d@giganews.com> <kfnpokrdor0.fsf@x-alumni2.alumni.caltech.edu> <o384ef$1irf$1@adenine.netfront.net> <c2dff3d8-e8f3-4c2a-901c-21682bb22918@googlegroups.com> <42d98296-3339-4814-8ba9-d8d71607e5bc@googlegroups.com> <ve-dndpVRPIarcXFnZ2dnUU7-RnNnZ2d@giganews.com>
Date: Mon, 19 Dec 2016 19:31:43 +0000
Message-ID: <87mvfr3ecg.fsf@gmail.com>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux)
Cancel-Lock: sha1:1gdz9Ba9jIWuml8/m0w1VILxR0M=
MIME-Version: 1.0
Content-Type: text/plain
Lines: 28
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-oVbGOzncRSLs8SjtRK8e2El7Fvg652riFSW5gvQTjQDOcYkaRI4zkgkL9kyLtrN6DG3jnFccb/aaa/z!Mz7kDUe8TtIhv38x9tB0TMbckcZD98XKi8gs5QWtveDridLVgzD9XN1k+ivTxMcSSmT+
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: 2878
Xref: csiph.com comp.lang.c++:47446

Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes:

> On 19/12/2016 14:40, gwowen wrote:
>> On Monday, December 19, 2016 at 12:46:44 PM UTC, leigh.v....@googlemail.com wrote:
>>> Answer me this: why do all std::list::sort implementations use merge sort
>>> rather than qsort?
>>
>> LMGTFY:
>> http://stackoverflow.com/questions/1717773/which-sorting-algorithm-is-used-by-stls-listsort
>> https://www.quora.com/What-algorithm-do-popular-C++-compilers-use-for-std-sort-and-std-stable_sort
>>
>> Short answer: These days they mostly use introsort.  And they do so
>> because introsort is faster, particularly on almost-sorted datasets,
>> and its good to avoid pathological behaviour, even if it isn't
>> necessary to meet the average-case complexity.
>>
>> They used to use merge-sort, because merge-sort is stable, and
>> quicksort/intro-sort is unstable unless you do some extra
>> bookkeeping (which does not increase the big-Oh behaviour).
>>
>> NB: All those intro/quick/merge sort behaviours are the same for
>> arrays, vectors and other containers.
>
> So qsort is 40% slower than merge sort on a linked list eh Gareth
> matey?.  So I was correct. 40. %. slower.

No.  You said average-case algorithmic complexity was worse.
That's not the same thing at all.