Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail
From: Keith Thompson <Keith.S.Thompson+u@gmail.com>
Newsgroups: comp.lang.c
Subject: Re: Isn't that beauty ? (no it's not)
Date: Fri, 20 Mar 2026 13:22:18 -0700
Organization: None to speak of
Lines: 45
Message-ID: <87tsua1cat.fsf@example.invalid>
References: <10otm7r$1ntrg$1@raubtier-asyl.eternal-september.org> <10pa4eg$2dtli$5@dont-email.me> <10pa78l$2fjaa$1@dont-email.me> <10palrv$2jpeu$2@dont-email.me> <10pbf0q$2rtq3$1@dont-email.me> <10pbg8f$2spms$2@dont-email.me> <10pbhud$2tbk0$2@dont-email.me> <10pcvr2$3ednq$2@dont-email.me> <20260318112151.000021dc@yahoo.com> <10pdu8k$3o60c$1@dont-email.me> <10pf3k4$690h$1@dont-email.me> <10pggfc$i81k$1@dont-email.me> <20260319122341.0000175d@yahoo.com> <10ph0rn$p9cu$1@dont-email.me> <IiUuR.931277$wcP9.580527@fx24.iad> <10pie5i$17mc2$3@dont-email.me> <87ldfmual7.fsf@example.invalid> <10pjbiv$1h0eh$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Fri, 20 Mar 2026 20:22:19 +0000 (UTC)
Injection-Info: dont-email.me; posting-host="af6390429069802727b3b4054313eed4"; logging-data="2003117"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/Oa85VlmVHct+0CcZRQY9B"
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:FPFRWSFEABdFNlvVu+ou1iZI0LY= sha1:RV3gedIXwl7iTWHmD+kWEgYOq3c=
Xref: csiph.com comp.lang.c:397122

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:
> On 2026-03-20 10:14, Keith Thompson wrote:
>> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:
>> [...]
>>> Quicksort (as opposed to qsort() - where the details are not
>>> obvious) is certainly a case for computer science lectures;
>>> I'd only have hoped that these CS basics are broadly known,
>>> also with non-CS educated or the many amateur programmers.
>> [...]
>> C doesn't specify which algorithm qsort() uses.  The name is almost
>> certainly derived from the name of the Quicksort algorithm, but the
>> C standard only says that the contents of the array are sorted.
>> A conforming but perverse implemention could use Bubblesort or
>> Bogosort.
>
> Yes, there's no [obvious] information; that's the dilemma![*]

I don't see a dilemma.  qsort() sorts.  No serious implementation is
going to use an algorithm with worse than O(n log n) performance.

>> Even the GNU libc documentation doesn't say what algorithm that
>> implementation uses.  (In the source code, I see references to
>> mergesort and heapsort.)
>
> Though the use of Mergesort is somewhat irritating (to me).
>
> But both are O(N log N), which is good to know. (And, frankly,
> I wouldn't have expected any worse O(N^2) algorithm here.)

In the glibc sources, stdlib/qsort.c has functions heapsort_r() and
qsort_r_mergesort().  I haven't examined it closely enough to know when
and how they're used.

> Janis
>
> [*] C++/STL has at least guarantees for the complexities.
> For me that would basically suffice. I don't necessarily need
> to know whether it's the concrete algorithm A or B.

You effectively have the same guarantee for qsort(), even though it's
not spelled out in the standard.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */