Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Fri, 3 Feb 2023 17:01:59 +0800 (CST)
From: "David Wang" <>
Subject: Re:Re: Re:Re:Re: Re:Re: qsort

At 2023-02-03 16:03:03, "Alexander Monakov" <> 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'.

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....


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.