mailing list of musl libc
 help / color / mirror / code / Atom feed
From: "David Wang" <00107082@163.com>
To: musl@lists.openwall.com
Subject: [musl] Re:Re: [musl] Re:[musl] Re:Re: [musl] Re:Re: [musl] qsort
Date: Fri, 3 Feb 2023 17:01:59 +0800 (CST)	[thread overview]
Message-ID: <180fda34.36d4.1861682d9fd.Coremail.00107082@163.com> (raw)
In-Reply-To: <841ab767-8f7c-4a4a-23ed-95901528a1b6@ispras.ru>



At 2023-02-03 16:03:03, "Alexander Monakov" <amonakov@ispras.ru> wrote:
>
>
>On Fri, 3 Feb 2023, David Wang wrote:
>
>> I think I was not reading the mail carefully enough,  and did not notice the
>> O(1) "in place" space complexity.
>
>It's not correct to claim that musl smoothsort improves on qsort by
>having O(1) space complexity rather than O(log n). The storage for
>Leonardo numbers in musl smoothsort grows as O(log n) as well, musl
>just allocates enough for the maximum possible 'n'.
>
>Alexander

Thanks for the clarification.

 Check with code history, it surprises me big time to know  that qsort in musl is never quick-sort, from the beginning qsort is heapsort because of O(nlgn) worse-case preformance and O(1) memory usage, and smoothsort is an improvement over heapsort....

David

  reply	other threads:[~2023-02-03  9:02 UTC|newest]

Thread overview: 34+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-01-20  1:49 Guy
2023-01-20 12:55 ` alice
2023-01-30 10:04   ` [musl] " David Wang
2023-02-01 18:01     ` Markus Wichmann
2023-02-02  2:12       ` [musl] " David Wang
2023-02-03  5:22         ` [musl] " David Wang
2023-02-03  8:03           ` Alexander Monakov
2023-02-03  9:01             ` David Wang [this message]
2023-02-09 19:03       ` Rich Felker
2023-02-09 19:20         ` Alexander Monakov
2023-02-09 19:52           ` Rich Felker
2023-02-09 20:18             ` Rich Felker
2023-02-09 20:27               ` Pierpaolo Bernardi
2023-02-10  4:10             ` Markus Wichmann
2023-02-10 10:00         ` [musl] " David Wang
2023-02-10 13:10           ` Rich Felker
2023-02-10 13:45             ` [musl] " David Wang
2023-02-10 14:19               ` Rich Felker
2023-02-11  5:12                 ` [musl] " David Wang
2023-02-11  5:44                   ` alice
2023-02-11  8:39                     ` Joakim Sindholt
2023-02-11  9:06                       ` alice
2023-02-11  9:31                         ` [musl] " David Wang
2023-02-11 13:35                         ` Rich Felker
2023-02-11 17:18                           ` David Wang
2023-02-16 15:15       ` David Wang
2023-02-16 16:07         ` Rich Felker
2023-02-17  1:35           ` [musl] " David Wang
2023-02-17 13:17           ` Alexander Monakov
2023-02-17 15:07             ` Rich Felker
2023-02-11  9:22     ` [musl] " Markus Wichmann
2023-02-11  9:36       ` [musl] " David Wang
2023-02-11  9:51       ` David Wang
2023-01-20 13:32 ` [musl] qsort Valery Ushakov

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=180fda34.36d4.1861682d9fd.Coremail.00107082@163.com \
    --to=00107082@163.com \
    --cc=musl@lists.openwall.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
Code repositories for project(s) associated with this public inbox

	https://git.vuxu.org/mirror/musl/

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).