Path: csiph.com!aioe.org!news.mixmin.net!news.unit0.net!border1.nntp.ams1.giganews.com!nntp.giganews.com!buffer1.nntp.ams1.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 19 Dec 2016 14:32:11 -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> <o396gv$cqe$1@node2.news.atman.pl> <87inqf698n.fsf@gmail.com> <o39fpj$jdq$1@node1.news.atman.pl>
Date: Mon, 19 Dec 2016 20:32:11 +0000
Message-ID: <87lgvb8xtg.fsf@gmail.com>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux)
Cancel-Lock: sha1:ox5jFRVoBK+sJ5QJ7y+6cay/k20=
MIME-Version: 1.0
Content-Type: text/plain
Lines: 39
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-yuUDrk2u+v2+tuieAIHv2mY0hKHi5FTrNxR4yKY9BYHSY1jUwME1RHyiz81EjODyMhe5w6GzaJfrvia!wsDTpRtpCJ+fRH4ejmnATUXXVO5BUhEOXLy/FyB1SdKcmlwZhTOCheiaiqqdkQTSfF47
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: 2943
Xref: csiph.com comp.lang.c++:47451

bartekltg <bartekltg@gmail.com> writes:

> On 19.12.2016 19:53, Gareth Owen wrote:
>> bartekltg <bartekltg@gmail.com> writes:
>>
>>> Jerry Coffin didn't understand the question. When you go to the
>>> second answer or to the second thread:
>>>
>>> http://stackoverflow.com/questions/1717899/which-sorting-algorithm-is-used-by-microsofts-stllistsort
>>>
>>> You get the real answer.
>>
>> I stand corrected[0].  See also here.
>>
>> http://stackoverflow.com/questions/5222730/why-is-merge-sort-preferred-over-quick-sort-for-sorting-linked-lists#5223117
>>
>> Leigh please note: The answer is *not* because quicksort on linked lists
>> is worse O(n log n) on average.
>
>
> I'm not sure, did you change your opinion?

Which opinion?

> std::list::sort is almost (*) always mergesort

I agree with this now.

> *) I didn't see implementation with different algorithm,
> but of course I can't be sure there is none ;-)

Of course.

> As a results, qsort work faster on vector and similar containers.

But only by a multiplicative factor, so time-big-Oh sense they're the
same. Or rather intro-sort and merge-sort are big-Oh-the-same
(worst case n*log n) but the multiplicative factor changes depending on
whether you can do random access or you have to traverse the list.