[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Fri, 3 Feb 2023 17:01:59 +0800 (CST)
From: "David Wang" <00107082@....com>
To: musl@...ts.openwall.com
Subject: Re:Re: Re:Re:Re: Re:Re: qsort
At 2023-02-03 16:03:03, "Alexander Monakov" <amonakov@...ras.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
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
